Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.95
BioShark
0 / 0 / 0
Регистрация: 16.12.2009
Сообщений: 38
04.02.2010, 21:21     Смежность и инцидентность ребер и вершин в графе. #1
Нужно взять любой граф (желательно попроще), ввести его програму. потом вводим 2 вершины, программа говорит, смежны ли они. затем вводим ребро и вершину, программа отвечает, инцидентны ли они,затем вводим 2 ребра, программа говорит смежны ли они, и на конец 4-е вводим вершину и прога возвращает ее степень.
К примеру взять граф квадрат с диагоналями...
Помогите, пожалуйста
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.02.2010, 21:21     Смежность и инцидентность ребер и вершин в графе.
Посмотрите здесь:

C++ Эффективный алгоритм подсчета расстояний от произвольной вершины до всех стальных вершин в графе
C++ Число вершин, удаленных от пары вершин по кротчайшим маршрутам каждой из следующих длин: 1, 2, 3 и т.д., для каждой пары вершин.
C++ Вычислить объемы тетрайда, гексаэдра и октаэдры, если длины ребер многогранников одинаковы и равны 3,55 см.
Напишите алгоритм вывода списка ребер неориентированного графа C++
Простой неориентированный граф задан списком ребер, выведите его представление в виде матрицы смежности C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
04.02.2010, 21:50     Смежность и инцидентность ребер и вершин в графе. #2
Ты нарисовал картинку. Это граф. Ты смотришь на него - и видишь ответы на все вопросы.
Любопытно, как этот граф видится твоим сознанием, и что происходит в это время в твоей
голове.
Какие включаются нейроны?
Почему странное слово "инцендентность" помогает тебе отыскать именно инцендентные
штуки.
Т.е. - в твоей головке существует ПРЕДСТАВЛЕНИЕ этого графа.
Я к чему. Начинать надо именно с ПРЕДСТАВЛЕНИЯ.
Ты сказал - квадрат с диагоналями (полный граф, кстати) - помоги компьютеру!
У него всего есть ДА и НЕТ и 32 бита в слове. Но этого ..... у него МНОГО.
Т.е. сначала надо придумать представления графа (их может быть несколько десятков -
зависит от задачи). Всунуть граф в линейную структуру машины. А уж только после этого
можно чего-то с нее спросить на еейном машинном языке
BioShark
0 / 0 / 0
Регистрация: 16.12.2009
Сообщений: 38
07.02.2010, 11:20  [ТС]     Смежность и инцидентность ребер и вершин в графе. #3
Цитата Сообщение от Day Посмотреть сообщение
Ты нарисовал картинку. Это граф. Ты смотришь на него - и видишь ответы на все вопросы.
Любопытно, как этот граф видится твоим сознанием, и что происходит в это время в твоей
голове.
Какие включаются нейроны?
Почему странное слово "инцендентность" помогает тебе отыскать именно инцендентные
штуки.
Т.е. - в твоей головке существует ПРЕДСТАВЛЕНИЕ этого графа.
Я к чему. Начинать надо именно с ПРЕДСТАВЛЕНИЯ.
Ты сказал - квадрат с диагоналями (полный граф, кстати) - помоги компьютеру!
У него всего есть ДА и НЕТ и 32 бита в слове. Но этого ..... у него МНОГО.
Т.е. сначала надо придумать представления графа (их может быть несколько десятков -
зависит от задачи). Всунуть граф в линейную структуру машины. А уж только после этого
можно чего-то с нее спросить на еейном машинном языке
это я нормально понимаю... но моих знаний по программированию не хватает чтобы это закодить, а здавать уже через день...
такчто если не трудно, напишите код
JKeeJ1e30
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
07.02.2010, 11:24     Смежность и инцидентность ребер и вершин в графе. #4
Парень, тебя ведь по пониманию проги долбать будут, так что мы, конечно, можем тебе написать, но сможешь ли ты потом объяснить это? Вопрос тяжелый.
ЗЫ: в таком деле комменты уже бесполезны
BioShark
0 / 0 / 0
Регистрация: 16.12.2009
Сообщений: 38
07.02.2010, 11:39  [ТС]     Смежность и инцидентность ребер и вершин в графе. #5
Цитата Сообщение от JKeeJ1e30 Посмотреть сообщение
Парень, тебя ведь по пониманию проги долбать будут, так что мы, конечно, можем тебе написать, но сможешь ли ты потом объяснить это? Вопрос тяжелый.
ЗЫ: в таком деле комменты уже бесполезны
Хотябы подскажите как ввести граф в программу...
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
07.02.2010, 11:41     Смежность и инцидентность ребер и вершин в графе. #6
Цитата Сообщение от BioShark Посмотреть сообщение
Хотябы подскажите как ввести граф в программу
Как матрицу смежности
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
07.02.2010, 13:00     Смежность и инцидентность ребер и вершин в графе. #7
Матрица смежности
http://www.intuit.ru/department/algorithms/graphsuse/2/
BioShark
0 / 0 / 0
Регистрация: 16.12.2009
Сообщений: 38
07.02.2010, 13:44  [ТС]     Смежность и инцидентность ребер и вершин в графе. #8
как ее ввести в программу?
M128K145
Эксперт C++
 Аватар для M128K145
8272 / 3491 / 142
Регистрация: 03.07.2009
Сообщений: 10,707
07.02.2010, 14:01     Смежность и инцидентность ребер и вершин в графе. #9
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
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
07.02.2010, 14:35     Смежность и инцидентность ребер и вершин в графе. #10
Нет есть еще помимо матриц смежности еще и списки смежности, с ними работать быстрее но они не входят ни в какую университетскую программу. С ними запаришься

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

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

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

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

Добавлено через 3 минуты
А вот тут уже лекция по спискам
http://www.intuit.ru/department/pl/plpascal/11/3.html
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.02.2010, 21:26     Смежность и инцидентность ребер и вершин в графе.
Еще ссылки по теме:

C++ Написать программу, которая выводит матрицу смежности графа с определенным количеством вершин и ребер
C++ Обмен информации правых вершин одного бинарного дерева на информацию левых вершин другого
C++ Ранжирование вершин на ориентированном графе без контуров по отношению к вершине

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
07.02.2010, 21:26     Смежность и инцидентность ребер и вершин в графе. #11
Будем задавать граф матрицей инцендентности вершин. Т.е. если вешины I, J соединены ребром,
то M[J][I] = M[I][J] = 1; (граф не ориентирован!)
Как вводить матрицу - тебе подсказал m128k145. Только тут небольшая специфика
Код
 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:
Код
   if (M[I][J] == 1) cout << "Инцендентны";
   else                 cout<< "Нет";
2) Пусть ребро задано своими вершинами I, J, Вершина - K
Код
if (I==K || J==K) cout<<"Инцендентны"ж
else                  cout<< "Нет";
3) Ребра I1 J1, I2 J2
Код
if (I1==I2 || I1==J2 || J1==I2 || J1==I2) cout<<"Инцендентны"ж
else                                                   cout<< "Нет";
4) Степень вершины J
Код
int deg = 0;
for i=0; i<N; i++) if (M[J][i]==1) deg++;
cout<< "deg="<<deg;
Счет вершин начинается с 0.
Yandex
Объявления
07.02.2010, 21:26     Смежность и инцидентность ребер и вершин в графе.
Ответ Создать тему
Опции темы

Текущее время: 21:05. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru