Спирина, М.С. Дискретная математика

Рис. 2.6. Графы: а — С9 (с областями At—A5); б — GI0 (с областями Аь Л2, Л , А5) циклу графа, являющемуся границей области. Поскольку рас­ сматриваются конечные графы, то плоский граф всегда является ограниченным подмножеством плоскости. Пусть М — планарный граф с внутренними областями. Тогда дополнение М, т.е. М' - М2\ М также может являться Областью. Например, граф G9 (рис. 2.6, а) выделяет в плоскости следующие области: А, с границей q\ Аг с границей (о, s, /); А3 с границей ( q , s, и, г, /); Ал с границей (р, и)\ А5 с границей (о, р, г). Множество А3 на рис. 2.6, б областью не является, так как пересечение А3Г\ Gl0 содержит точку Q , не при­ надлежащую никакому циклу. Теорема 2.5 (Эйлера). Связный плоский граф с п вершинами и т ребрами разбивает плоскость на г областей (включая внешнюю), причем п - т + г - 2. Задача 17 «О трех колодцах». Проложить дорожки от трех до­ мов к каждому из трех колодцев так, чтобы никакие две дорожки не пересекались (рис. 2.7). Граф называется двудольным, если его вершины разбиты на два непересекающихся подмножества: V= V, \J V2, а ребра связывают вершины только из разных классов (не обязательно все пары). Если каждая вершина множества У] связана а в с ребром с каждой вершиной множества I I v2, то двудольный граф называется -------- полным двудольным и обозначается Кт„, В где т = | К[|, п - 1 У2\. Примером двудоль­ ного полного графа А"3 3 является граф к к задаче 17, которую также назыв «Три дома — три колодца», показывая Рис. 2.7. Иллюстрация этим два непересекающихся множества к задаче «О трех колодцах» вершин графа. 76