|
Задача на графы
|
||
|---|---|---|
Участник
Откуда: здесь была правда.<br /><br />Слоган: Делфи жив!!!
Сообщения: 30 377 |
||
| 22.01.2011, 23:14 |
|
|
|
|
|
Задача на графы
|
|||
|---|---|---|---|
|
#18+
В учебнике дана задача: Show that every graph with 2 or more nodes contains two nodes that have equal degrees. Я знаю что это неправда для графов в которых разрешены петли. Там можно у всех нод сделать разную степень. А вот для простых графов это похоже на правду, только не могу понять с какой стороны подступится. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.01.2011, 22:48 |
|
||
|
Задача на графы
|
|||
|---|---|---|---|
Участник
|
|||
|
#18+
Если я правильно понял с албанского наречия, то надо доказать, что у любого графа с 2 и более точками найдется 2 узла с одинаковым количеством связей. Если да, то запросто. Допустим, это не так (у всех степени разные). Если в графе N вершин, то всего имеем N разных возможных степеней (0 ... N-1). А раз степени разные, то все эти значения используются, и тогда у одной из вершин степень 0, т.е. она на отшибе, а у другой - степень N-1, т.е. она связана со всеми другими. Это противоречие. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.01.2011, 23:14 |
|
||
|
Задача на графы
|
|||
|---|---|---|---|
|
#18+
За подсказку спасибо. PS: А при чем здесь албанский? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.01.2011, 08:29 |
|
||
|
Задача на графы
|
|||
|---|---|---|---|
|
#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 ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 24.01.2011, 10:31 |
|
||
|
|
start [/forum/topic.php?fid=16&fpage=91&tid=1343182]: |
0ms |
get settings: |
6ms |
get forum list: |
9ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
38ms |
get topic data: |
6ms |
get forum data: |
1ms |
get page messages: |
22ms |
get tp. blocked users: |
1ms |
| others: | 200ms |
| total: | 287ms |
| 0 / 0 |
