|
Задача на графы
|
||
|---|---|---|
Участник
Откуда: здесь была правда.<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/moderation_log.php?user_name=maxxxxxxxx]: |
0ms |
get settings: |
8ms |
get forum list: |
15ms |
get settings: |
9ms |
get forum list: |
15ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
51ms |
get topic data: |
12ms |
get forum data: |
3ms |
get page messages: |
48ms |
get tp. blocked users: |
2ms |
| others: | 719ms |
| total: | 890ms |
| 0 / 0 |
