6. Наследственные свойства графов. (1176847), страница 2

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

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

, wn−1 не могут быть одновременно смежны c какой-товершиной u ∈ V 0 , откудаn−1X(dG (wi ) − (n − 2)) ≤ p(n − 2).i=1Следовательно,|E | ≤==(n−2)(p 2 −r 2 )+ r (r 2−1) + (n−1)(n−2)+ p(n − 2)22(n−1)(n−2)(p 2 −r 2 )+(n−1)2 (n−2)+2p(n−1)(n−2)+ r (r 2−1)2(n−1)22(n−2)((p+(n−1)) −r )+ r (r 2−1) .2(n−1)==ЗадачиНаследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаЗадачиЧисло ребер в графах без подграфов KnДоказательство нижней оценки.Граф — k-дольный, k ≥ 2, если его вершины можно разбитьна k непересекающихся частей (долей) так, что смежны тольковершины из разных частей.Граф с долями из n1 , . .

. , nk вершин, в котором смежны любыедве вершины из разных долей, называется полнымk-дольным графом Kn1 ,...,nk .Графы Kp1 ,...,pn−1 при p = (n − 1)s + r , где 0 ≤ r ≤ n − 2,p1 = . . . = pr = (s + 1), pr +1 = . . . = pn−1 = s,показывают достижимость верхней оценки.Наследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаЗадачи1.

Построить планарный граф G = (V , E ) с наибольшимчислом ребер, если:1)2)3)4)|V | = 4;|V | = 5;|V | = 6;|V | = 7.2. Существует ли планарный граф G = (V , E ), если:1)2)3)4)|V | = 7, |E | = 16;|V | = 8, |E | = 17;|V | = 6 и в G ровно 7 граней;|V | = 7 и в G ровно 12 граней.ЗадачиНаследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаЗадачи3. Построить граф G = (V , E ) без треугольников снаибольшим числом ребер, если:1)2)3)4)|V | = 5;|V | = 6;|V | = 7;|V | = 8.4.

Построить граф G = (V , E ) без полного графа Kn снаибольшим числом ребер, если:1)2)3)4)|V | = 5,|V | = 6,|V | = 7,|V | = 8,n = 3;n = 3;n = 4;n = 4.ЗадачиНаследственные свойстваПланарные графыГрафы без треугольниковТеорема ТуранаЗадачиЛитература к лекции1. Емеличев В.А., Мельников О.И., Сарванов В.И., ТышкевичР.И. Лекции по теории графов. М.: Либроком, 2009. С.

155–159.2. Харари Ф. Теория графов. М.: Мир, 1973. С. 152–153, 30–31.3. Bondy J.A., Murty U.S.R. Graph theory. Springer, 2008.С. 301–302.Наследственные свойстваПланарные графыГрафы без треугольниковКонец лекцииТеорема ТуранаЗадачи.

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

Список файлов лекций