|
Действия ...
|
22.01.2011, 23:14
|
|||
|---|---|---|---|
|
|||
Задача на графы |
|||
|
|
Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
22.01.2011, 22:48
|
|||
|---|---|---|---|
Задача на графы |
|||
|
#18+
В учебнике дана задача: Show that every graph with 2 or more nodes contains two nodes that have equal degrees. Я знаю что это неправда для графов в которых разрешены петли. Там можно у всех нод сделать разную степень. А вот для простых графов это похоже на правду, только не могу понять с какой стороны подступится. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
22.01.2011, 23:14
|
|||
|---|---|---|---|
|
|||
Задача на графы |
|||
|
#18+
Если я правильно понял с албанского наречия, то надо доказать, что у любого графа с 2 и более точками найдется 2 узла с одинаковым количеством связей. Если да, то запросто. Допустим, это не так (у всех степени разные). Если в графе N вершин, то всего имеем N разных возможных степеней (0 ... N-1). А раз степени разные, то все эти значения используются, и тогда у одной из вершин степень 0, т.е. она на отшибе, а у другой - степень N-1, т.е. она связана со всеми другими. Это противоречие. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
23.01.2011, 08:29
|
|||
|---|---|---|---|
Задача на графы |
|||
|
#18+
За подсказку спасибо. PS: А при чем здесь албанский? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
24.01.2011, 10:31
|
|||
|---|---|---|---|
Задача на графы |
|||
|
#18+
On 22.01.2011 22:48, White Owl wrote: > /Show that every graph with 2 or more nodes contains two nodes that have equal > degrees./ Думаю, методом от противного и из определения дуги (не петли) можно доказать. Posted via ActualForum NNTP Server 1.4 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=16&mobile=1&tid=1343182]: |
0ms |
get settings: |
9ms |
get forum list: |
18ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
175ms |
get topic data: |
9ms |
get forum data: |
2ms |
get page messages: |
35ms |
get tp. blocked users: |
1ms |
| others: | 236ms |
| total: | 493ms |
| 0 / 0 |
