Смежность и инцидентность ребер и вершин в графе.

@BioShark · Регистрация: 16.12.2009

Студворк — интернет-сервис помощи студентам

Нужно взять любой граф (желательно попроще), ввести его програму. потом вводим 2 вершины, программа говорит, смежны ли они. затем вводим ребро и вершину, программа отвечает, инцидентны ли они,затем вводим 2 ребра, программа говорит смежны ли они, и на конец 4-е вводим вершину и прога возвращает ее степень.
К примеру взять граф квадрат с диагоналями...
Помогите, пожалуйста

Day · 04.02.2010, 21:50

Ты нарисовал картинку. Это граф. Ты смотришь на него - и видишь ответы на все вопросы.
Любопытно, как этот граф видится твоим сознанием, и что происходит в это время в твоей
голове.
Какие включаются нейроны?
Почему странное слово "инцендентность" помогает тебе отыскать именно инцендентные
штуки.
Т.е. - в твоей головке существует ПРЕДСТАВЛЕНИЕ этого графа.
Я к чему. Начинать надо именно с ПРЕДСТАВЛЕНИЯ.
Ты сказал - квадрат с диагоналями (полный граф, кстати) - помоги компьютеру!
У него всего есть ДА и НЕТ и 32 бита в слове. Но этого ..... у него МНОГО.
Т.е. сначала надо придумать представления графа (их может быть несколько десятков -
зависит от задачи). Всунуть граф в линейную структуру машины. А уж только после этого
можно чего-то с нее спросить на еейном машинном языке

@BioShark · 07.02.2010, 11:20 **[ТС]**

Сообщение от Day

Ты нарисовал картинку. Это граф. Ты смотришь на него - и видишь ответы на все вопросы.
Любопытно, как этот граф видится твоим сознанием, и что происходит в это время в твоей
голове.
Какие включаются нейроны?
Почему странное слово "инцендентность" помогает тебе отыскать именно инцендентные
штуки.
Т.е. - в твоей головке существует ПРЕДСТАВЛЕНИЕ этого графа.
Я к чему. Начинать надо именно с ПРЕДСТАВЛЕНИЯ.
Ты сказал - квадрат с диагоналями (полный граф, кстати) - помоги компьютеру!
У него всего есть ДА и НЕТ и 32 бита в слове. Но этого ..... у него МНОГО.
Т.е. сначала надо придумать представления графа (их может быть несколько десятков -
зависит от задачи). Всунуть граф в линейную структуру машины. А уж только после этого
можно чего-то с нее спросить на еейном машинном языке

это я нормально понимаю... но моих знаний по программированию не хватает чтобы это закодить, а здавать уже через день...
такчто если не трудно, напишите код

@JKeeJ1e30 · 07.02.2010, 11:24

Парень, тебя ведь по пониманию проги долбать будут, так что мы, конечно, можем тебе написать, но сможешь ли ты потом объяснить это? Вопрос тяжелый.
ЗЫ: в таком деле комменты уже бесполезны

@BioShark · 07.02.2010, 11:39 **[ТС]**

Сообщение от JKeeJ1e30

Парень, тебя ведь по пониманию проги долбать будут, так что мы, конечно, можем тебе написать, но сможешь ли ты потом объяснить это? Вопрос тяжелый.
ЗЫ: в таком деле комменты уже бесполезны

Хотябы подскажите как ввести граф в программу...

@M128K145 · 07.02.2010, 11:41

Сообщение от BioShark

Хотябы подскажите как ввести граф в программу

Как матрицу смежности

@odip · 07.02.2010, 13:00

Матрица смежности
http://www.intuit.ru/departmen... aphsuse/2/

@BioShark · 07.02.2010, 13:44 **[ТС]**

как ее ввести в программу?

@M128K145 · 07.02.2010, 14:01

BioShark, а как вводят матрицы в программу?

C++
1
2
3
4
5
int matr[5][5];
int i, j;
for(i = 0; i < 5; ++i)
    for(j = 0; j < 5; ++j)
        std:cin>>matr[i][j];

@JKeeJ1e30 · 07.02.2010, 14:35

Нет есть еще помимо матриц смежности еще и списки смежности, с ними работать быстрее но они не входят ни в какую университетскую программу. С ними запаришься

Добавлено через 2 минуты
http://ru.wikipedia.org/wiki/%... 1%82%D0%B8

Добавлено через 1 минуту
Тут и матрицы и списки

Добавлено через 1 минуту
Ой сорри только матрицы

Добавлено через 5 минут
Тут по графам дофига всего

Добавлено через 3 минуты
А вот тут уже лекция по спискам
http://www.intuit.ru/departmen... /11/3.html

Day · 07.02.2010, 21:26

Будем задавать граф матрицей инцендентности вершин. Т.е. если вешины I, J соединены ребром,
то M[J][I] = M[I][J] = 1; (граф не ориентирован!)
Как вводить матрицу - тебе подсказал m128k145. Только тут небольшая специфика

C++
1
2
3
4
5
6
 for(J=0; J<N; J++) {
   M[J][J] = 0;  
   for(I=J+1; I<N;  I++) cin>>M[J][I];
   M[J][I] = M[I][J];
 }
// Т.е. вводим только то что, под (или над) диагональю

1) Инцендентность вершин I, J:

C++
1
2
   if (M[I][J] == 1) cout << "Инцендентны";
   else                 cout<< "Нет";

2) Пусть ребро задано своими вершинами I, J, Вершина - K

C++
1
2
if (I==K || J==K) cout<<"Инцендентны"ж
else                  cout<< "Нет";

3) Ребра I1 J1, I2 J2

C++
1
2
if (I1==I2 || I1==J2 || J1==I2 || J1==I2) cout<<"Инцендентны"ж
else                                                   cout<< "Нет";

4) Степень вершины J

C++
1
2
3
int deg = 0;
for i=0; i<N; i++) if (M[J][i]==1) deg++;
cout<< "deg="<<deg;

Счет вершин начинается с 0.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .
Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .	SDL3 для Web (WebAssembly): Синхронизация спрайтов SDL3 и тел Box2D 8Observer8 04.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-sync-physics-sprites-sdl3-c. zip На первой гифке отладочные линии отключены, а на второй включены:. . .	SDL3 для Web (WebAssembly): Идентификация объектов на Box2D v3 - использование userData и событий коллизий 8Observer8 02.03.2026 Содержание блога Финальная демка в браузере. Итоговый код: finish-collision-events-sdl3-c. zip Сканируйте QR-код на мобильном и вы увидите, что появится джойстик для управления главным героем. . . .

@BioShark 0 / 0 / 1 Регистрация: 16.12.2009 Сообщений: 38

	Смежность и инцидентность ребер и вершин в графе. 04.02.2010, 21:21. Показов 4399. Ответов 10 Метки нет (Все метки) Нужно взять любой граф (желательно попроще), ввести его програму. потом вводим 2 вершины, программа говорит, смежны ли они. затем вводим ребро и вершину, программа отвечает, инцидентны ли они,затем вводим 2 ребра, программа говорит смежны ли они, и на конец 4-е вводим вершину и прога возвращает ее степень. К примеру взять граф квадрат с диагоналями... Помогите, пожалуйста 0

Day 1180 / 990 / 83 Регистрация: 29.10.2009 Сообщений: 1,385
	04.02.2010, 21:50
	Ты нарисовал картинку. Это граф. Ты смотришь на него - и видишь ответы на все вопросы. Любопытно, как этот граф видится твоим сознанием, и что происходит в это время в твоей голове. Какие включаются нейроны? Почему странное слово "инцендентность" помогает тебе отыскать именно инцендентные штуки. Т.е. - в твоей головке существует ПРЕДСТАВЛЕНИЕ этого графа. Я к чему. Начинать надо именно с ПРЕДСТАВЛЕНИЯ. Ты сказал - квадрат с диагоналями (полный граф, кстати) - помоги компьютеру! У него всего есть ДА и НЕТ и 32 бита в слове. Но этого ..... у него МНОГО. Т.е. сначала надо придумать представления графа (их может быть несколько десятков - зависит от задачи). Всунуть граф в линейную структуру машины. А уж только после этого можно чего-то с нее спросить на еейном машинном языке 0

@JKeeJ1e30 12 / 12 / 0 Регистрация: 04.02.2010 Сообщений: 45
	07.02.2010, 11:24
	Парень, тебя ведь по пониманию проги долбать будут, так что мы, конечно, можем тебе написать, но сможешь ли ты потом объяснить это? Вопрос тяжелый. ЗЫ: в таком деле комменты уже бесполезны 0

@odip 7176 / 3234 / 82 Регистрация: 17.06.2009 Сообщений: 14,164
	07.02.2010, 13:00
	Матрица смежности http://www.intuit.ru/departmen... aphsuse/2/ 0

@BioShark 0 / 0 / 1 Регистрация: 16.12.2009 Сообщений: 38
	07.02.2010, 13:44 [ТС]
	как ее ввести в программу? 0

@JKeeJ1e30 12 / 12 / 0 Регистрация: 04.02.2010 Сообщений: 45
	07.02.2010, 14:35
	Нет есть еще помимо матриц смежности еще и списки смежности, с ними работать быстрее но они не входят ни в какую университетскую программу. С ними запаришься Добавлено через 2 минуты http://ru.wikipedia.org/wiki/%... 1%82%D0%B8 Добавлено через 1 минуту Тут и матрицы и списки Добавлено через 1 минуту Ой сорри только матрицы Добавлено через 5 минут Тут по графам дофига всего Добавлено через 3 минуты А вот тут уже лекция по спискам http://www.intuit.ru/departmen... /11/3.html 0