0,98 Mb.страница17/17Дата конвертации03.10.2011Размер0,98 Mb.Тип Смотрите также: 17 ^ W III.15.Планарные графы Укладкой графа на произвольной поверхности называется такое изображение его на этой поверхности, что ребра графа пересекаются только в его вершинах. Сферической укладкой называется укладка графа на сфере. Плоской укладкой называют укладку графа на плоскости. Граф, имеющий плоскую укладку, называется плоским. Граф, изоморфный плоскому, называется планарным. На рис.39 (а) изображен планарный граф, (б) и (в) две его плоские укладки. Любой простой планарный граф можно уложить на плоскости так, чтобы его ребра были прямолинейными отрезками. Укладка графа на плоскости равносильна его укладке на сфере, поскольку существует взаимно однозначное соответствие точек сферы и плоскости, устанавливаемое стереографической проекцией. Два основных непланарных графа: полный граф ^ К5 и полный двудольный граф К3,3 называют графами Куратовского. Граф планарен тогда и только тогда, когда он не содержит подграфа, стягиваемого к одному из графов Куратовского. Укладка планарного графа на плоскости делит её на области, называемые гранями. Если грань имеет конечную площадь, назовем её конечной, иначе бесконечной гранью. На рис.40 конечные грани это g1, g2, g3, а g4 бесконечная грань. Соотношение между числом вершин, ребер и граней в планарном графе было установлено Эйлером. (Формула Эйлера) Если связный граф планарен и имеет v вершин, r ребер и g граней, то vP PrP+PgP=P2. Доказательство проводится индукцией по числу ребер. Пусть r=0. Тогда в планарном связном графе имеется только одна вершина и одна бесконечная грань. И утверждение теоремы верно. Пусть теперь теорема верна для любого связного планарного графа с (rP]P1) ребрами. Добавим к графу еще одно ребро е. При этом возможно три случая: а) е петля, тогда число вершин остается неизменным, число граней увеличивается на единицу, и, поскольку число ребер также увеличилось на единицу, формула остается верной; б) е соединяет две различные вершины графа. Тогда одна из граней расщепляется на две, добавляя единицу к g. Число вершин неизменно, а число ребер увеличилось на единицу. И теорема верна. в) е висячее ребро. Тогда число вершин увеличивается на единицу, число граней остается прежним и, поскольку число ребер также увеличилось на единицу, формула снова верна. Следствие 1. Пусть ^ G планарный граф с v вершинами, r ребрами, g гранями и k компонентами. Тогда vP PrP+PgP=PkP+1. Доказательство. Применяя теорему Эйлера для каждой отдельной компоненты, получим: (*)PviP PriP+PgiP=P2, где i=1,2, ,k номер компоненты. При этом , . И, поскольку для каждой компоненты учитывается бесконечная грань, то общее число граней . Просуммируем (*) по числу компонент: . Отсюда или . И утверждение доказано. Следствие 2. Если G связный простой планарный граф с r ребрами, g гранями и v вершинами, где , то . Доказательство. По теореме о степенях вершин в графе . Заметим, что каждое ребро ограничивает не более двух граней. Назовем степенью грани число ребер на её границе. Заметим, что понятие степени грани аналогично понятию степени вершины, в связи с чем можно сформулировать аналогичное утверждение о степенях граней: , где gi iPая грань. Поскольку граф простой, т.е. не имеет петель и параллельных ребер, и число вершин , то степень каждой грани также должна быть больше, либо равна трем. Т.е. deg(gi) 3 для любого i=1,2, ,g. Поэтому и отсюда . Но из теоремы Эйлера число граней . Т.о. и отсюда , что и требовалось доказать. Следствие 3. Графы Куратовского K5 и K3,3 не являются планарными. Доказательство. Число ребер в K5 равно 10, число вершин 5. И по следствию 2 получим: 9 10, что не верно. Поэтому K5 не может быть планарным. Для графа K3,3: r=9, v=6, а число граней по теореме Эйлера должно быть равно 9P6+2=5. Заметим, что в графе K3,3 нет циклов, короче 4. Поэтому степень каждой грани и . С другой стороны и отсюда . Т.е. , что не верно. Поэтому K3,3 не может быть планарным. Следствие 4. В
Курс лекций Часть I учебное пособие рпк «Политехник» Волгоград 2005 4 чел. помогло.
W III.15.Планарные графы - Курс лекций Часть I учебное пособие рпк «Политехник» Волгоград 2005
Комментариев нет:
Отправить комментарий