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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.95
BioShark
0 / 0 / 0
Регистрация: 16.12.2009
Сообщений: 38
#1

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

04.02.2010, 21:21. Просмотров 2758. Ответов 10
Метки нет (Все метки)

Нужно взять любой граф (желательно попроще), ввести его програму. потом вводим 2 вершины, программа говорит, смежны ли они. затем вводим ребро и вершину, программа отвечает, инцидентны ли они,затем вводим 2 ребра, программа говорит смежны ли они, и на конец 4-е вводим вершину и прога возвращает ее степень.
К примеру взять граф квадрат с диагоналями...
Помогите, пожалуйста
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.02.2010, 21:21
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Смежность и инцидентность ребер и вершин в графе. (C++):

Написать программу, которая выводит матрицу смежности графа с определенным количеством вершин и ребер - C++
Всем доброго времени суток!!! Передо мной стоит задача: написать программу, которая выводит матрицу смежности графа с определенным...

Разделить граф таким образом, чтобы после обрезания ребер, у поддеревьев оставалось четное количество вершин - C++
Разделить граф таким образом, чтобы после обрезания ребер, у поддеревьев оставалось четное количество вершин. Желательно реализовать через...

Ранжирование вершин на ориентированном графе без контуров по отношению к вершине - C++
Помогите сделать алгоритм по данному коду. Задание: Написать и исследовать программу, осуществляющюю ранжирование вершин на ориентированном...

Эффективный алгоритм подсчета расстояний от произвольной вершины до всех стальных вершин в графе - C++
Реализовать в виде программы и исследовать эффективный алгоритм подсчета расстояний от произвольной вершины до всех стальных вершин в...

Число вершин, удаленных от пары вершин по кротчайшим маршрутам каждой из следующих длин: 1, 2, 3 и т.д., для каждой пары вершин. - C++
Число вершин, удаленных от пары вершин по кротчайшим маршрутам каждой из следующих длин: 1, 2, 3 и т.д., для каждой пары вершин. ...

Обмен информации правых вершин одного бинарного дерева на информацию левых вершин другого - C++
Помогите пожалуйста с задачей Написать программу обмена информации правых вершин одного бинарного дерева на информацию левых вершин...

10
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
04.02.2010, 21:50 #2
Ты нарисовал картинку. Это граф. Ты смотришь на него - и видишь ответы на все вопросы.
Любопытно, как этот граф видится твоим сознанием, и что происходит в это время в твоей
голове.
Какие включаются нейроны?
Почему странное слово "инцендентность" помогает тебе отыскать именно инцендентные
штуки.
Т.е. - в твоей головке существует ПРЕДСТАВЛЕНИЕ этого графа.
Я к чему. Начинать надо именно с ПРЕДСТАВЛЕНИЯ.
Ты сказал - квадрат с диагоналями (полный граф, кстати) - помоги компьютеру!
У него всего есть ДА и НЕТ и 32 бита в слове. Но этого ..... у него МНОГО.
Т.е. сначала надо придумать представления графа (их может быть несколько десятков -
зависит от задачи). Всунуть граф в линейную структуру машины. А уж только после этого
можно чего-то с нее спросить на еейном машинном языке
0
BioShark
0 / 0 / 0
Регистрация: 16.12.2009
Сообщений: 38
07.02.2010, 11:20  [ТС] #3
Цитата Сообщение от Day Посмотреть сообщение
Ты нарисовал картинку. Это граф. Ты смотришь на него - и видишь ответы на все вопросы.
Любопытно, как этот граф видится твоим сознанием, и что происходит в это время в твоей
голове.
Какие включаются нейроны?
Почему странное слово "инцендентность" помогает тебе отыскать именно инцендентные
штуки.
Т.е. - в твоей головке существует ПРЕДСТАВЛЕНИЕ этого графа.
Я к чему. Начинать надо именно с ПРЕДСТАВЛЕНИЯ.
Ты сказал - квадрат с диагоналями (полный граф, кстати) - помоги компьютеру!
У него всего есть ДА и НЕТ и 32 бита в слове. Но этого ..... у него МНОГО.
Т.е. сначала надо придумать представления графа (их может быть несколько десятков -
зависит от задачи). Всунуть граф в линейную структуру машины. А уж только после этого
можно чего-то с нее спросить на еейном машинном языке
это я нормально понимаю... но моих знаний по программированию не хватает чтобы это закодить, а здавать уже через день...
такчто если не трудно, напишите код
0
JKeeJ1e30
12 / 12 / 0
Регистрация: 04.02.2010
Сообщений: 45
07.02.2010, 11:24 #4
Парень, тебя ведь по пониманию проги долбать будут, так что мы, конечно, можем тебе написать, но сможешь ли ты потом объяснить это? Вопрос тяжелый.
ЗЫ: в таком деле комменты уже бесполезны
0
BioShark
0 / 0 / 0
Регистрация: 16.12.2009
Сообщений: 38
07.02.2010, 11:39  [ТС] #5
Цитата Сообщение от JKeeJ1e30 Посмотреть сообщение
Парень, тебя ведь по пониманию проги долбать будут, так что мы, конечно, можем тебе написать, но сможешь ли ты потом объяснить это? Вопрос тяжелый.
ЗЫ: в таком деле комменты уже бесполезны
Хотябы подскажите как ввести граф в программу...
0
M128K145
Эксперт С++
8293 / 3513 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
07.02.2010, 11:41 #6
Цитата Сообщение от BioShark Посмотреть сообщение
Хотябы подскажите как ввести граф в программу
Как матрицу смежности
0
odip
Эксперт С++
7158 / 3220 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
07.02.2010, 13:00 #7
Матрица смежности
http://www.intuit.ru/department/algorithms/graphsuse/2/
0
BioShark
0 / 0 / 0
Регистрация: 16.12.2009
Сообщений: 38
07.02.2010, 13:44  [ТС] #8
как ее ввести в программу?
0
M128K145
Эксперт С++
8293 / 3513 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
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];
0
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
0
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
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.
0
07.02.2010, 21:26
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.02.2010, 21:26
Привет! Вот еще темы с ответами:

Как найти число вершин и ребер в графе окресности каждой пары вершин - C#
Как найти число вершин и ребер в графе окресности каждой пары вершин? Добавлено через 5 минут В принципе, я написал, но мне сказал...

Количество ребер в графе - Дискретная математика
Какое максимальное количество ребер может быть в простом слабо связном ориентированном графе на 10 вершинах, не являющемся сильно связным?

Сколько ребер в графе? - Дискретная математика
Помогите, пожалуйста разъяснить мне данную задачку по графам. Верно ли я решила задание? Условие: Дан граф G-дерево. Количество вершин...

Вывести формулу ребер в графе - Дискретная математика
Вывести формулу ребер в графе при известных степенях вершин. Это если полустепень исхода больше нуля d(i)&gt;0 , или полустепень захода...


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

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru