Дискретная математика

158 Плоским графом называется граф, изображенный на плоскости так, что никакие два его ребра (или, вернее, представляющие их линии) не пересекаются нигде, кроме инцидентной или обоим вершины Граф изоморфный плоскому графу, назьшается танарным графом. На рис. 5.30 изображены два графа; оба они планарные, но плоский только один из них, который расположен справа. Пусть Ki - полный граф с пятью вершинами, а Кз_з - полный двудольный граф с шестью Рис. 5.30 вершинами, множество вершин которого разбито на два подмножества: К/ и Кг. Множества Fy и V2 содержат по три вершины, и каждая вершина из F/ соединяется ребром с каждой из V2, и наоборот, каждая вершина из V2. соединяется ребром с каждой из Vi- Теорема 5.20. Графы Ks и Кз^ непланарны. Доказательство. Докалсем для Ks. Так как - полный граф, то он содержит цикл длины 5, который можно записать v/ v j V4 г'5 v; и без потери общности считать, этот цикл изображается правильным пятиугольником, см. рис. 5.31, а), Ребро (vs.v^) лежит либо целиком внутри пятиугольника, либо целиком вне его. Рассмотрим случай, когда лежит внутри пятиугольника (второй случай будет аналогичным). Поскольку и не пересекают (VS^VT), ТО они должны лежать вне пятиугольника. Ребро (VS.V}) очевидно, должно быть внутри пятиугольника. Тогда как ни проводить ребро оно обязательно пересекается либо с {vs,vj), либо с ( У /. УД ). Таким образом, граф К} непланарен. Рассмотрим граф Кз,з. Пусть V]={v,,v3,vs}, V2={v2,v4,v6}- По условию vi соединено с V2, с Vj,v j с V.,, V4 С V5, V5 с VG, и VFI с V/, следовательно, имеем цикл длины 6, который без уменьшения общности можно изобразить в виде правильного шестиугольника, см. рис. 5.31, б). В Кз^з, кроме того, есть ребра (VhV4), (V2,Vs) И {V3,V^. И з этих трех ребер два а) б) Рис, 5.31