Теория графов и комбинаторика

ОоигЙЯ роль графов Kj- и J с лугмчавтоя том,, что либой нрпла'тарнк'п граф содержит один из них, т.е. они яаляшзтоя по с;ущоо?иу «дпногнещцйгл ноплапарнимк графами. Этот факт являатой о()Дйр*;;ан!1('1 азвеотноИ теореш П1нгрягина-4{уратонокого. 5II.3. Теоаема Понтрягина-Кутатовокого Ьводом понятие гомеоморфизма графов, которо • аопользуег'я при формулировко Taop8f «n Пситрягина-Кураторского. Даа графа ^ иН пазипаютоя гом9омор$1шш (или f">SBeoTB0H- uiir.r.i с точиоотьв до вершин степени 2), если они изомо^^фда или их M07ico получить (о точностью до изоморфизма) из одного и того же rpaja после конечного числа подразйиеюШ рейер. Например, графы, изображенный на ряо.И.З, гомеоморфны. Рио.И.З Заметим, что подразбиение рейра сводится к включению новой вершиш степени 2, а это на может влзшть .;б манарнооть графа. Хдовема I I 1 (Понтрягин-Куратов-'Гсий). Гра" ^ планарен тогда и только тогда, когда он не содержит подграфа, гомеоморф- ЙОГО КУ или К ^ , 3 • Доказательство этой тео. )Ш опуокаем. Пользуясь этой теоре­ мой, можно, напртлер, вняокить, что граф ff , изображенный На рис.П.4, непланарный, так как.оодержит подграф , гомеошрф- 3 Й ! О Л Т . 4 . Шевтся д|5?гой критерий планаряооти, 01Шра«мг!5'зя, на понятие отягйваемооти - рафов»' Теореиа Н.б.ГраЙ ff' планарен тогда и только тогда; когда он не содершт подграфа, отягвваемого к Ку или К 3 3 . Например, граф ( рис .ИД ) является стягиваемым к и поэтому I'f) планарен. 68