В.А. Носов - Комбинаторика и теория графов (1023552), страница 16

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 16)

Используя теорему Эйлера можно доказывать непланарность конкретныхграфов.Пусть G – планарный граф. Обозначим через ϕk – число граней, ограниченных kребрами.Поскольку рассматриваются графы без петель и параллельных ребер, тоϕ0 = ϕ1 = ϕ2 = 0.Справедливы следующие соотношения:f = ϕ3+ϕ4+ ...2m = 3⋅ϕ3+4ϕ1+...В первом соотношении просуммированы все грани, во втором – ребра, ограничивающие каждую грань, при этом каждое ребро учитывается дважды.Рассмотрим граф К3, 3. Для него n = 6, m = 9.

Пусть K3, 3 – плоский граф. Тогдадолжно быть f = 9 – 6+2 = 5 граней.100Для графа K3, 3 нет циклов длины 3, поэтому ϕ3 = 0. Следовательно, должнобыть выполнено5 = ϕ4+ϕ5+ ...18 = 4⋅ϕ4+5ϕ5+ ...Отсюда получаем (т.к. ϕk ≥ 0), что –2 ≥ 0 – противоречие.Рассмотрим теперь граф К5. Для него n = 5, m = 10. Если бы граф К5 был плоским, то должно быть f = 10 – 5+2 = 7.

Следовательно, должно быть выполнено7 = ϕ4+ϕ5+ ...20 = 4⋅ϕ4+5ϕ5+ ...Отсюда следует, что –1 ≥ 0 – противоречие.В качестве упражнения предлагается доказать, что граф Е4 – (четырехмерныйкуб) – не является планарным.4. Имеется несколько критериев планарности графа. Приведем без доказательства критерий Понтрягина-Куратовского. Для этого определим понятие гомеоморфизмаграфа.

Операцией разбиения ребра e = (u, v) называют операцию замены ребра е двумяребрами e1 = (u, w) и e2 = (w, v), где w – новая вершина. Два графа называют гомеоморфными, если они могут быть получены из одного графа с помощью операций разбиенияребер.СправедливаТеорема (Понтрягин-Куратовский). Граф планарен тогда и только тогда, когдаон не содержит подграфов, гомеоморфных К3, 3 или К5.5.

Для характеристики непланарных графов используются различные меры, изкоторых укажем две. Толщина графа G есть число t(G) – наименьшее число его планарных подграфов, объединение которых дает граф G. Очевидно, что толщина планарногографа есть 1.Приведем значение толщины некоторых графов:n + 7t( Kn ) =  6  n + 1t( E n ) =  4 mnt( Km,n ) =  2(m + n − 2) Здесь [x], ]x[ – ближайшие целые для х, удовлетворяющие [x] ≤ x ≤ ]x[.101Род графа G определяется как минимальное число ручек γ(G), которые надоприкрепить к сфере, чтобы уложить граф G.

Ясно, что для плоского графа G γ(G) = 0поскольку укладка на плоскости равносильна укладке на сфере.Приведем значения рода некоторых графов.γ ( E n ) = 1 + ( n − 4 ) 2 n− 3 ( n − 3)( n − 4 ) γ ( Kn ) = 12 ( m − 2 )( n − 2 ) γ ( Km,n ) = 4102§ 7. Раскраска графовПусть G = (V, E) – некоторый граф. Пусть {1, 2, ..., k} – множество "цветов".Отображение f: V → {1, 2, ..., k} называют k-раскраской вершин графа G. К-раскрасканазывается правильной, если∀(v1, v2)(v1, v2) ∈ E ⇒ f(v1) ≠ f(v2).т.е.

смежные вершины получают различную окраску. Граф G называется kраскрашиваемым, если для него существует правильная k-раскраска. Наименьшее k, длякоторого граф G является k-раскрашиваемым, называется хроматическим числом графаG (обозначение: x(G)). Если x(G) = k, то граф G называется k-хроматическим.Существует ряд задач кибернетики, которые приводят к раскраске графа (задачисоставления расписаний, обслуживания и др.).Заметим сначала, что для любого натурального n существует граф G, такой, чтоx(G) = n.

Примером такого графа является Kn. Очевидно, что x(Kn) = n.Ясно, что 1-хроматические графы это графы, состоящие из изолированных вершин. 2-хроматические графы – это двудольные графы и только они.В настоящее время нет описания k-хроматических графов при k ≥ 3. Нет такжеэффективных алгоритмов нахождения хроматического числа графа. Однако, имеютсяхорошие оценки хроматического числа.Теорема 1. Пусть p – максимальная степень вершин графа G = (V, E). Тогдасправедливо неравенствоx(G) ≤ p+1 Индукция по n = |V|. Выберем произвольную вершину v ∈ V и удалим ее вместе с инцидентными ей ребрами. Получим граф G′, у которого максимальная степеньвершин р′, причем р′ ≤ p. Число вершин у G′ равно n – 1 и по индукции для G′ имеется(p′+1)-раскраска, а значит и (p+1)-раскраска.

Тогда (p+1) – раскраску для G можно получить так: окрасим v в цвет, отличный от цветов вершин, смежных с ней, число которыхне больше p. Для планарных графов данную оценку можно уточнить (используем обозначения предыдущего параграфа).Теорема 2. Любой планарный граф 6-раскрашиваем. Заметим сначала, что для связного планарного графа G = (V, E) выполнено2m – 3f ≥ 0.103Это следует из равенств:f = ϕ3+ϕ4+ ...2m = 3ϕ3+4ϕ4+ ...По теореме Эйлера должно выполняться n – m+f = 2.

Отсюда получаем 3n –m ≥ 6.Покажем теперь, что в планарном графе существует вершина степени не выше5.Пусть напротив, все вершины имеют степень не меньшую, чем 6. Поскольку∑ deg(v) = 2m , то отсюда следует, что должно быть 2m ≥ 6n или m ≥ 3n.Два последние неравенства приводят к противоречию.Теперь доказываем утверждение теоремы индукцией по n = |V|.Пусть для всех планарных графов G = (V, E) с |V| < n0 утверждение верно.

ПустьG – граф с |V| = n0. По предыдущему, в G есть вершина v степени не выше 5. Удалим vвместе со смежными ей ребрами и получим граф G′ с n0 – 1 вершинами, планарный. Попредположению индукции x(G′) ≤ G. Пусть v1, ..., vk – вершины G′, смежные с v. Имеемk ≤ 5. Для раскраски G используем для v цвет, отличный от цветов v1, ..., vk. Следовательно, x(G) ≤ G. Усложнив рассуждения, можно доказать, что x(G) ≤ 5 для всякого планарногографа. Гипотеза 4х красок для планарного графа была сформулирована А. Кэли в 1878году и утверждала, что x(G) = 4.Данная гипотеза была подтверждена в 1978 году Аппелем Т. и Хакеном М. Соответствующее доказательство использовало ЭВМ и пока оно не имеет проверки в традиционном понимании.104§ 8.

Потоки в сетях.В этом пункте будут рассмотрены основы важного направления, связанного сизучением потоков в сетях. На практике постоянно приходится сталкиваться с различного рода сетями - например, транспортные сети, сети связи, электрические сети и т.п.,поэтому математическое изучение таких сетей имеет важное прикладное значение. Втеории сетей большую роль играют графические методы. Предварительно рассмотримпример.v1424v312w42v24Рис. 1.Пусть отправитель v хотел бы послать получателю w несколько предметов.

Числа надугах графа на рис. 1 обозначают максимальное число предметов, которое можно послать по соответствующим каналам. Для отправителя v представляет существенный интерес знать, какое максимальное количество предметов он может послать, не превышаядопустимую пропускную способность каждого канала.Будем называть сетью N ориентированный граф, каждой дуге которого e приписано неотрицательное действительное число ω(e), называемое ее пропускной способностью. Другими словами, сеть N есть пара (Г, ω), где - Г - ориентированный граф, а ω функция, отображающая множество дуг графа Г в множество неотрицательных действительных чисел. По аналогии с терминологией для ориентированных графов можно определить полустепень исхода вершины v для сети N как сумму пропускных способностейдуг вида (v, x).

Аналогично определяется полустепень захода вершины. Ясно, что суммаполустепеней исхода всех вершин в сети равна сумме полустепеней захода.Будем предполагать, что ориентированный граф Г содержит точно одну вершину v, у которой полустепень захода равна нулю, и точно одну вершину ω, у которой полустепень исхода равна нулю. Эти вершины называются источником и стоком соответственно.105Пусть дана сеть N = (Г, ω). Определим поток через сеть как функцию ϕ, сопоставляющую каждой дуге e из Г неотрицательное действительное число ϕ(e), котороеназывается потоком через e, причем функция ϕ удовлетворяет условиям:1) ϕ(e) ≤ ω(e) для любой дуги e.2) В сети (Г, ϕ) полустепень исхода равна полустепени захода для любой вершины, отличной от источника и стока. Данные условия означают, что поток через любую дугу не превышает ее пропускной способности и что поток “входящий” в любуювершину (отличную от источника и стока) равен “исходящему” из нее потоку.

Ясно, чтосумма потоков через дуги, инцидентные источнику, равна сумме потоков через дуги,инцидентные стоку. Эта сумма называется величиной потока. Нас будут интересоватьпотоки, имеющие наибольшее значение, эти потоки называются максимальными. Например, для сети на рис. 2 максимальным потоком будет поток, равный 6. Он изображенна рис. 2 ниже.v13v02v221210w4v3Для сети N = (Г,ω) определим понятие разреза, как такого множества А дуг графа Г, чтолюбая ориентированная простая цепь из v в ω содержит дугу из А. Пропускной способностью разреза А называется сумма пропускных способностей принадлежащих А дуг.Минимальным называется такой разрез, у которого пропускная способность принимаетнаименьшее значение.

Характеристики

Список файлов книги