Форум программистов, компьютерный форум, киберфорум
Наши страницы
Дискретная математика
Войти
Регистрация
Восстановить пароль
 
udov
7 / 7 / 0
Регистрация: 10.01.2013
Сообщений: 59
#1

Орграф

06.11.2013, 21:27. Просмотров 445. Ответов 2
Метки нет (Все метки)

Доказать, что в любом конечном ациклическом орграфе существуют вершины
с нулевой степенью исхода и нулевой степенью захода.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.11.2013, 21:27
Ответы с готовыми решениями:

Орграф
Доказать, что для любой вершины х є X орграфа G=(X,Г) найдется МНМ, содержащие...

Орграф
Помогите построить изображение графа, указать степени вершин графа.По матрице...

Орграф - дискретная математика!
Ребята! Не получается сделать задачи! Задача 1 В Стране Дождей возможны три...

Теория отношений (матрица, орграф)
Помогите составить матрицу и орграф. Примерно представляю как это делается. Не...

Знаковый орграф - как посчитать, хотя бы первый шаг
Примем для знакового орграфа, изображенного на рис., что V(исх)= (0, 0, 0, 0),...

2
Mysterious Light
Эксперт по математике/физике
3942 / 1920 / 383
Регистрация: 19.07.2009
Сообщений: 2,942
Записей в блоге: 21
07.11.2013, 00:59 #2
Достаточно легко:

Допустим, ацикличный граф имеет N вершин. Выбираем любую, имя ей A1.
Если она не имеет ни одного исходящего инцидетного ребра, суждение справедливо.
Если имеет хотя бы одно, то выберем произвольное и последуем вдоль, попадём в вершину A2.
Если A2 не имеет ни одного исходящего ребра, то суждение истинно. Иначе повторяем процедуру и переходим к A3.
Продолжаем построение, но не далее, чем на N шагов.
Возможны N ситуаций: либо мы остановились на A1, либо на A2, либо на A3 и т.д., либо всё-таки дошли до AN.
Прошу обратить внимание, что в любом из первых (N-1) случаев суждение истинно.
В последнем случае последовательность A1,A2,...,AN не имеет повторений в силу ацикличности, а потому множество {A1,A2,...,AN} содержит все вершины графа. Граф ацикличен, а поэтому AN не может иметь исходящего ребра. В этом случае суждение также оказывается истинным.
Вывод: в каждом из N случаев суждение выполняется. Полная индукция нам даёт истинность исходного суждения.

Прошу обратить внимание, что в этом доказательстве использовалась полная (конечная) индукция и рекурсия конечной заведомо известной глубины. Здесь не использовался приём доказательства от противного или что-то другое столь же неочевидно... мне редко попадаются задачи, которые можно было б решить так.
2
Байт
Эксперт C
18106 / 11961 / 2485
Регистрация: 24.12.2010
Сообщений: 24,092
07.11.2013, 02:00 #3
Цитата Сообщение от Mysterious Light Посмотреть сообщение
В последнем случае последовательность A1,A2,...,AN не имеет повторений в силу ацикличности, а потому множество {A1,A2,...,AN} содержит все вершины графа.

Не по теме:

Почти все задачи ТС - просто на принцип Дирихле.

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.11.2013, 02:00

орграф на С++
Пожалуйста, помогите! Может, кто-то когда-то писал такую программу: в файле...

Орграф
Прошу,перевидете просто на С,ибо С++ не юзаю совсем.Заранее благодарю. ...

Орграф, элементарный путь
Необходимо найти элементарный путь длинны l на орграфе. Не пойму как это можно...


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

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

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