Графы и транспортные сети ...

Сообщение №3616 от IDNM 28 мая 2002 г. 23:58
Тема: Графы и транспортные сети ...

Помогите если не затруднит:

1.Как показать, что в любом планарном графе без петель и кратных рёбер найдётся
вершина степени не более чем пять ?

2.Доказать, что в транспортной сети величина всякого потока не превосходит
пропускной способности всякого разреза ?


Отклики на это сообщение:

> Помогите если не затруднит:

> 1.Как показать, что в любом планарном графе без петель и кратных рёбер найдётся
> вершина степени не более чем пять ?
Будем добавлять к графу ребра до тех пор, пока он может оставаться планарным. Всякий максимальный планарный граф имеет число ребер m=3n-6, где n-число вершин. Пусть ni-число вершин степени i. Тогда 2(3n-6)=m=3n3+4n4+5n5+...>=
3(n3+n4+n5)+6(n6+n7+...) Отсюда, поскольку n=n1+n2+..., имеем n3+n4+n5>=4, то есть в планарном графе существует по крайней мере 4 вершины степени не превышающими 5


> 2.Доказать, что в транспортной сети величина всякого потока не превосходит
> пропускной способности всякого разреза ?
Это теорема Форда-Фалкерсона. Интересно, где это ее предлагают в качестве упражнения доказать?


Пардон, невнимательно читал,спрашивается же, что величина потока не превосходит пропускной способности разреза. Теорема Форда-Фалкерсона-это то, что они равны. Тогда я вопроса не понимаю-это же очевидно.


> Пардон, невнимательно читал,спрашивается же, что величина потока не превосходит пропускной способности разреза. Теорема Форда-Фалкерсона-это то, что они равны. Тогда я вопроса не понимаю-это же очевидно.

то что величина любого потока не превосходит пропускной способнотси любого разреза - это следствие из леммы о разрезах и потоках
а лемма такая: для любого потока и для любого разреза, разделяющего источник и сток, величина потока равна потоку через этот разрез минус поток через обратный разрез
вот...


Физика в анимациях - Купить диск - Тесты по физике - Графики on-line

Реклама:
Rambler's Top100