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

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

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

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

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

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

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

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

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

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

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

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

Реализуйте представление дерево в виде списка ребер в С++ - C++
Реализуйте представление дерево в виде списка ребер (массива одно связанных списков) С режимами работы: 1)Добавление элементов. ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Day
1154 / 959 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
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
Эксперт С++
8283 / 3502 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
07.02.2010, 11:41     Смежность и инцидентность ребер и вершин в графе. #6
Цитата Сообщение от BioShark Посмотреть сообщение
Хотябы подскажите как ввести граф в программу
Как матрицу смежности
odip
Эксперт С++
7155 / 3295 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
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
Эксперт С++
8283 / 3502 / 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];
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++
Реализуйте представление графа в виде списка ребер (массива одно связанных списков) С режимами работы:1)Добавление элементов.2)Просмотр...

Напишите алгоритм вывода списка ребер неориентированного графа - C++
Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка ребер. Вот начало #include &lt;iostream&gt;...

Вычислить объемы тетрайда, гексаэдра и октаэдры, если длины ребер многогранников одинаковы и равны 3,55 см. - C++
Вычислить объемы тетрайда, гексаэдра и октаэдры, если длины ребер многогранников одинаковы и равны 3,55 см.

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

Поиск на графе - C++
Доброго времени суток. Мне не совсем понятна реализация в коде поиска на графе в высоту и ширину. Т.к. в книге они описаны не совсем...


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

Или воспользуйтесь поиском по форуму:
Day
1154 / 959 / 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.
Yandex
Объявления
07.02.2010, 21:26     Смежность и инцидентность ребер и вершин в графе.
Ответ Создать тему
Опции темы

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