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

графу точек оочлвнеяия C(ff-), в Ka^ieoTBe шожаотва S ^ примем множество 3 = [Ьс , а семейотво Р ~ i ^= } онределвм так; S t = { 6 6 S : «cC- E.bi: =f,r»3 . То г да , о'зввидио, jQ( f ) ^ С (6-) • Изоморфизмом является отображение . Таким образом, вершиной графа € (&•) можно очитать MHOssoTBo «Злоков, имеющих общую точку сочленения. ГЖМ 8. ДВУДОЛЕШ-Г^ ГРАФЫ. ПАЮСОЧКСАЙШ ^8.1. Оппеделениа ДВУДОЛЬНОГО гпаДа. T e o o f g Канига Рассмотрим одан чаотный клаоо графов, назнваемнх двудольны­ ми, которые тшроко чополъзуютоя при решении прикладных задич. Граф (ysCv/jyjHasHBseTOH двудольным (или б и г р а ^м ) , если его множество варшш V мокно разбить на два поданокеотва V, к так, чтобы каждое ребро графа $ соединяло веришг" ча разных множеотя. Двудольный граф обознечается тек: € -(\/ч)Ч^,Х) . кеотаа Vj называются долями графа & . Как видно из опреде­ ления, если ) - двудольный гр5ф, о в каждом из шю- жес 3 У| н V i нет смежных вершин. Это условие можат быть положе­ но в оонову определения r*iyдольного rpai^. Двудольный граф б ~ (V<, Уд,,)^) наэнваатс5я полным, если б X . полный двудольный граф обозначаетоя , где . На рио.8.1 показа­ ны два двудолышх графа. е) б) Рио.6.1 1 ^ $ назнваетоя звездой. Понятие двудольного графа может быть обобщено. Граф S'-(VfX) называется V) -дольнш, оола. оущоотвует разбиение множеотва V его вершин такое, что каздов раброагеХ ооединяет вершины ка разных поданюкеотв У/, Ниокаотае , I = <, и называются дошла и -дольного графа (г -(^1,'^JL X ) , Полным называехоя такой И -дольный граф, в котором каздая BepiiinHa любой доли oMssma оо всеми йерамнаш ор— 4Р1