Спец часть (часть 1) (3 поток) (2015) (by Кибитова) (Ответы на спец часть), страница 9

Тогда на S мыиполучимr гранями.Отсюда согласноследствию1 p – q + r связного= 2. Следствиегеометрическуюреализациюнекоторогографа 2с доказано.p вершинами, q рёбрами§20.ДоказательствонепланарностиграфовKиK.53,3и r гранями. Отсюда согласно следствию 1 p – q + r = 2. Следствие 2 доказано.Понтрягина-Куратовского(доказательствов одну сторону).§20.

ТеоремаДоказательствонепланарности графовK5 и K3,3.Понтрягина-Куратовского(доказательствов одну сторону).§20. ТеоремаДоказательствонепланарности графовK5 и K3,3.Определение 1. Графом K5 называется граф с пятьювершинами, в котором каждая параТеорема Понтрягина-Куратовского (доказательство в одну сторону).вершинсоединена ребром.Определение1. Графом K5 называется граф с пятью вершинами, в котором каждая паравершинсоединенаребром.Определение 1.

Графом K5 называется граф с пятью вершинами, в котором каждая паравершин соединена ребром.K5K5Теорема 6. Граф K5 не планарен.K5Теорема 6. Граф KДопустим,Доказательство.что для графа K5 существует планарная реализация. Так как5 не планарен.Допустим,что дляграфа K5 существуетграф Доказательство.Kдля Kэтойпланарнойреализациисправедливапланарнаяформула реализация.Эйлера p – qТак+ rкак= 2.5 связен,6.тоТеоремаГраф5 не планарен.граф Доказательство.K5 связен,то дляэтойпланарнойреализациисправедливаформулаЭйлераp–q+r=Посколькув графеK5 имеемp=5иq=10,точисловсехгранейдолжноравнятьсяr=2–p2.+Допустим, что для графа K5 существует планарная реализация. Так какПосколькувграфеKимеемp=5иq=10,точисловсехгранейдолжноравнятьсяr=2–p+2.+графq = 7.грани1, 2,реализации…, r и пустьпри обходеформулаi-ой гранипо периметру5занумерованыK5Пустьсвязен,то дляэтой планарнойсправедливаЭйлераp – q + r =(по+Посколькуqкраю)= 7.

ПустьграниKзанумерованы…,этомr ичислопустьприреброобходеi-ойгранипо периметруеёпроходитсярёбер.pТакприкаждоеобходитсядважды(онов графе= 5 каки1,q 2,=10,товсехгранейдолжноравнятьсяr = являет2 –(поp+5qiимеемr при этом каждое ребро обходится дважды (оно являетеёкраю)проходитсяqрёбер.Таккакi+ qстороной= 7. Пусть2,…,rипустьприобходеi-ойгранипопериметру(посядлягранидвухзанумерованыграней), то ∑1,q=2q=20.Новкаждойгранинеменеетрёхсторон.ri =1 iеё сторонойкраю) проходитсякаккаждоеобходится(оносторон.являетсядля двух qграней),то ∑qпри= 2этомq = 20. Но вреброкаждойграни недваждыменее трёхi рёбер. Такi =1r irПоэтомуq≥3длявсехi.Отсюдаq≥3r=21.Получаем20≥21—противоречие.Знаi∑i=r1i =q1qi =i ≥23qr==2021.. Нося сторонойдвухграней),то ∑в каждойгранинепротиворечие.менее трёх сторон.Поэтомуqi ≥ для3 длявсехi.

ОтсюдаПолучаем20≥21—Зна∑i =r 1 i реализации.чит, для графа K5 не существует планарнойПоэтомуq≥3длявсехi.Отсюда3rграф= 21 .с Получаем20 ≥ 21 — aпротиворечие.Значит,дляграфаKнесуществуетпланарнойi∑i =1 qi ≥реализации.5 2. Графом K3,3 называетсяОпределениешестью вершинами1, a2, a3, b1, b2, b3, в2. ГрафомK3,3планарнойназываетсяграфс шестьювершинамиa1, a2,рёберa3, b1,нет.b2, b3, вкоторомai соединенаребромс каждойвершинойbj и другихчит, Определениедля каждаяграфа Kвершинареализации.5 не существуеткоторомкаждаявершинаaсоединенаребромскаждойвершинойbидругихрёбернет.ijОпределение 2.

Графом K3,3 называется граф с шестью вершинами a1, a2, a3, b1, b2, b3, вa1a2a3котором каждая вершина ai соединенаa1 ребромaс2 каждойa3вершиной bj и других рёбер нет.a1a2a3b1b1b2b2K3,3b2K3,3b3b3b1b3rеё сторонойкраю) проходитсякаккаждоеобходится(оно сторон.являетi рёбер. Таксядля двух qграней),то ∑qпри= 2этомq = 20.

Но вреброкаждойграни недваждыменее трёхi =1 irr q = 2 q = 20 . Но в каждой грани не менее трёх сторон.ся стороной для двух граней), тоПоэтому qi ≥ 3 для всех i. Отсюда∑∑i=i1r=1 iqi ≥ 3r = 21 . Получаем 20 ≥ 21 — противоречие. ЗнаПоэтомуqi ≥ 3Kдлявсех i. Отсюда ∑i =1 qi ≥реализации.3r = 21 . Получаем 20 ≥ 21 — противоречие.

Значит,для графа5 не существует планарнойГрафом K3,3планарнойназываетсяграф с шестью вершинами a1, a2, a3, b1, b2, b3, вчит, Определениедля графа K5 не2.существуетреализации.которомкаждаявершинаaсоединенаребромс каждойвершинойbj и другихiОпределение 2. ГрафомK3,3 называется графс шестьювершинамиa1, a2рёбер, a3, b1нет., b2, b3, вкотором каждая вершина ai соединенаребромскаждойвершинойbидругихрёбернет.jaaa123a1a2a3b1b2b3b1Kb3,32b3K3,3Теорема 7. Граф K3,3 не планарен.Доказательство.что для графа K3,3 существует планарная реализация. ТакТеорема 7. Граф KДопустим,3,3 не планарен.как графK3,3 связен, тоДопустим,для этой планарнойреализациисправедливаформулареализация.Эйлера p – Такq+Доказательство.что для графаK3,3 существуетпланарная+какr =граф2.

ПосколькувграфеKимеемp=6иq=9,точисловсехгранейдолжноравняться3,3 планарной реализации справедлива формула Эйлера p – q +K3,3 связен, то для этойr+ =r =2 2.– Посколькуp + q = 5.Так же,в доказательстветеоремы,получаем,чтов графеK3,3 какимеемp = 6 и q = 9, топредыдущейчисло всех гранейдолжноравнятьсяr∑=r q2i =– 2pq =+18q , =где5.qiТакже,каквдоказательствепредыдущейтеоремы,получаем,что— число сторон в i-ой грани.

Но в графе K3,3 нет циклов длины 3. Поir=1∑i =1 qi = 2q = 18 , где qi — число сторон в i-ой грани. Но в графе K3,3 нет циклов длины 3. По20этому в каждой грани не менее 4 сторон.20 Следовательно, qi ≥ 4 для всех i. Отсюдаrграни не18менее4 сторон.Следовательно,qi ≥графа4 дляi. Отсюдаq ≥в4rкаждой= 20 . Получаем≥ 20 —противоречие.Значит, дляK3,3всехне существует∑этомуi =1r ir = 20 . Получаем 18 ≥ 20 — противоречие. Значит, для графа K3,3 не существует∑i=1 qi ≥ 4реализации.планарнойпланарнойреализации.Определение3.

Подразделением ребра (a, b) называется операция, состоящая в слеОпределениедующихдействиях: 3. Подразделением ребра (a, b) называется операция, состоящая в следующихдействиях:1) удаление(a, b),удаление (a,b), вершины c,2)1) добавлениеновойдобавлениерёберновой(a,вершиныc,3)2) добавлениеc) и (c, b).3) добавление(a,называетсяc) и (c, b). подразделением графа G, если H можно получить изОпределение4. рёберГраф HОпределение4. ГрафH называетсясвоихподразделениемграфа G, если H можно получить изG путёмконечного числаподразделенийрёбер.G путёмконечного5.числаподразделенийсвоихрёбер.ОпределениеДва графаназываютсягомеоморфными,если существуют их подраздеОпределение5.Дваграфаназываютсягомеоморфными,если существуют их подразделения, которые изоморфны.ления,которыеизоморфны.Теорема8 (Понтрягина-Куратовского).Граф является планарным тогда и только тоТеорема(Понтрягина-Куратовского).Граф является планарнымтогдагда, когдаон не8содержитни одного подграфа, гомеоморфногографам K5 илиK3,3и.

только тогда,Доказательство.когда он не содержитниодногоподграфа,гомеоморфногографамKилиНеобходимость. Пусть G — планарный. Допустим,чтоK3,3он. содержит5Доказательство.Необходимость.— планарный.Допустим,что он содержитподграфG1, гомеоморфныйграфу K5 илиПустьK3,3. GРассмотримпланарнуюреализациюграфа G.подграфG1, гомеоморфныйграфу мыK5 илиK3,3. Рассмотримпланарную реализациюG.1Удаливлишниевершины и рёбра,получимпланарную реализациюподграфа Gграфа1. Но GУдаливлишниевершиныирёбра,мыполучимпланарнуюреализациюподграфаG.НоGгеометрически — это граф K5 или K3,3 с точками на рёбрах. Если проигнорировать эти1 точки,1— это графреализациюK5 или K3,3 сграфаточкамина рёбрах.проигнорироватьточки,тогеометрическимы получим планарнуюK5 илиK3,3. НоЕслиэто невозможнов силуэтитеорем1томыполучимпланарнуюреализациюграфаKилиK.Ноэтоневозможновсилутеорем153,3и 2.

Необходимость доказана.и 2.ДостаточностьНеобходимостьбездоказана.доказательства.Достаточность без доказательства.§21. Теорема о раскраске планарных графов в пять цветов.§21. Теорема о раскраске планарных графов в пять цветов.Лемма 1. Для любой геометрической реализации на плоскости связного планарного граДля любой геометрическойреализации на плоскости связного планарного графа с q Леммарёбрами1.выполняетсяравенство:фа с q рёбрами выполняется равенство:r∑ qq ==22qq, ,∑ri =1i =1iiгде суммирование ведётся по всем граням (включая внешнюю).где Доказательство.суммирование ведётсяпо всемследуетграням из(включаявнешнюю).Равенствотого, чтоу каждого ребра две стороны и приДоказательство.

Равенство следует из того, что у каждого ребра две стороны и при3. Логика 1-го порядка. Выполнимость и общезначимость. Общаясхема метода резолюций. Базовые символы. Предметные переменныеПредметные константы Функциональные символы Предикатные символыVar = {x1,x2,...,xk,...}; Const = {c1,c2,...,cl,...};Func = {f(n1) (n2)(nr),f,...,f ,...}; 12r(m1)(m2)(ms )Pred = {P,P,...,P, . . . }.АЛФАВИТАЛФАВИТТройка ⟨Const,Pred,Func⟩ называется сигнатурой алфавита.Логические связки и кванторы.Логическиесвязкии кванторы.Конъюнкция(логическоеИ)&Дизъюнкция (логическое ИЛИ)_Конъюнкция (логическое И)&Отрицание(логическое НЕ)¬Дизъюнкция (логическое ИЛИ)_Импликация (логическое ЕСЛИ-ТО) !.Отрицание(логическое НЕ)¬Кванторвсеобщности(�длякаждого�)8Импликация (логическое ЕСЛИ-ТО) !.Квантор существования (�хотя бы один�) 9Квантор всеобщностикаждого�) 8СИНТАКСИС:ТЕРМЫ(�дляИ ФОРМУЛЫКвантор существования (�хотя бы один�) 9Знаки препинания.СИНТАКСИС:ТЕРМЫ И ФОРМУЛЫ,,Знакипрепинания.РазделительОпределениетерма.Скобки(РазделительОпределение терма.)Скобки()Терм� это  x, если x 2 Varx � переменная;Терм� этоc,еслиc2Constcконстанта;xx Varx � переменная;(n)(n)2 Funcтерм.cf (t1 , t2 , .

. . , tn ) , если cf 2 Constcсоставной� константа;(n)(n)t,t,...,t�термыf (t1 , t2 , . . . , tn ) , если2nFuncсоставной терм.1 2ft1 , t2 , . . . , tn � термы  СИНТАКСИС: ТЕРМЫ И ФОРМУЛЫTerm � множество термов заданного алфавита.СИНТАКСИС:ТЕРМЫ И ФОРМУЛЫTermмножествотермов заданногоалфавита.Vart ��множествопеременных,входящихв состав терма t.Определениеформулы.Varпеременных,входящихтермв составтерма t.t(x1t , �x2 ,множество. . . , xn ) �формулы.записьобозначающаяt, у которогоОпределениеФормула�этоVar✓{x,x,...,x}.t(x1 , x2 , . . . , xn ) � записьобозначающаяt1 2n терм t, у которого  Формула�этоVar✓{x,x,...,x}.t12nатомарная формула(m) (t , t , .