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

iPOT-"va И . I . Если P^(\/,X) - лроотой г р ' " , то Дог.азагадьстпо. Иуоть % - произвольная вершина, Приовоим ей одйн КЗ «ротов. Выберем нераокрашенную яока вершину 2^ и ей .вот, ке оовпадающи'^ о цветами смежных ей вершин, позкойно, гак как c/{V"i) ^ j . Повторим этот процеоо до "чх пор, когда окажутоя раокрашенш" i вое верины. В резуль- чато по.чуч;ш ('!•'"') -раокраоку. Очевплдо, Х(&)^ аС(г)+1 Д Я Я ПОЛНЫХ ,графов И ЦИКЛОВ не- чагкой длинц. Оказываетоя, что для воех ооталъных граТюв Теорема I I . й . П УСТЬ^'-FL /Jl -HANYOTOFI граф и IV|=f >^J6 . Тогда Х(.^) € /+ ' г д еб ' ~ поро1йдвнный подграф графа € '- SCS'; , l T ^ G ' \ . Доказатвльотйо. Пуоть ^<,б-)=;У1 . Ос5означим Н - минималь­ ный подграф графа ^ , для которого X f Н) - , Из шнималъноо- ти Н оледует, что V t r e H 1К(Н-1Г)=цМ . т . е . каждая вершина Н является нооителем нового цвета. Следовательно, VireИ Отовда получаем ц0П''"ку неравенотв: 4 I +W I O - X . §11.2. Планарнооть , Бывают ойтуации, когда определение графа о точностью до иаомо]1физма окаг -ваетоя недоотаточны.. Например, еоли граф иэо- '1ражав'г некоторую электричеокую охему и вое проводкики раополе- гавтоя в одной плоскости, то возникает проблема отыокания тако­ г о раоположения диаграммы г р ь ^ , при котором ребра (проводники) пересекаютоя только в вершинах. Такая укладка грэ-М оущеотвует не всегда. В общем случае раооматриваетоя укладка графа на про­ извольной nOBt^jXHOOTH. Граф G- иазываетоя уложенным на поверхности S , если его диаграмму можно нарисовг 'ь на поверхности 5 так, чтобы ребра перБсекалиоь только в верпшнах. TpaiJ называетоя плоским, еоли он уложен на плоокооти^и планарпым, аоли он изоморфен шгоокому. Разделимый граф планарен тогда и только тогда, когда планарвы е г о блоки, поэтому в дальнейшем можно рассматривать только я е - рааделйшв гре<*-'. Теорема Н.Э. Любой простой планерный граф моано уложить на илоскооти гак, чтобы вое ребра ивобраяалиоь отрезками пряшх. Укладываемооть графа па плоокооти и яа сфере аквивалентнн, т . е . если граф укладаваетоя на плоокооти, тс он укладывается и 66