В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 55
Текст из файла (страница 55)
300 Пусть Н=()е, ео ) — гиперграф, О Ф Г вЂ” )е. Нодгиперграфолб порожденным множеством вершин е", называется гипсрграф ХХ' =(Р', ео'), где ео" =(е': е' = ей )е' ФИ, ее ее). Вершины и и о гиперграфа Н называются связанными, если и =- о или в Н существует (и, о)-цепь. Легко Рис. 68.4 видеть, что отношение связанности есть отношение эквивалентности на множестве вершин гиперграфа.
Классы этого отношения называются областями связности гиперграфа Н, а порожденные областями связности подгиперграфы называются компонентами (связными компонен тали) гнперграфа Н. Количество компонент гиперграфа Н ооозпачается через й(Н). Если й(Н)=1, то гиперграф Н называется связным. Очевидно, что й(Н)= ЦК(Н)), где й(К(Н)) — число компонент графа К(Н).
У т в е р ж д е н и е 68 1. (п, т)-гиперграф Н не содерисит циклов тозда и только тогда, когда ()е! — 1) = п — /г(П). ееен с. Очевидно, что гиперграф Н пе содержит циклов тогда и только тогда, когда его кенпгово представление К(П) является лесом. Но граф К(Н) имеет 1г(П) компонент, т+и вершин и ~., ~е! ребер. Поэтому на осноеЕа Н ванин следствия 13.4 имеем )е! = т+ и — )г(П), еЕО Н т. е ((е! — 1) = п — Й(Н).
еее и Утверждение 682. Гиперграф циклов тогда и только тогда, когда для Н не содержит любого непустого 801 подмножества сс ' '= со Н выполняется неравенство (),'!= Х ((! ! — 1). ,! еаза ! еаза 1 с' Достаточность. Предположим, что Н содержит цикл оь еь оп ег, ..., о„е„оь Тогда, положив сс = (еь ег, ..., ед, имеем , ~-! () е!=!() е; =~() (е ~ог) < еаза" ! ~ г=г гег <~г !е ~ог(=~ ((ег! — 1), что противоречит неравенству (1). Необходимость.
Если гиперграф Н =()т, сс) не содержит цикла, то для любого о' ж Ю гиперграф Н' =(т", д' ) с множеством вершин К'= () е также не еил' содержит цикла. Поэтому на основании утверждения 68.1 имеем Х Це! — 1)=! () е! — к(Н')(! () е~. <) ам 8' ! еаза ! еас Поскольку всякому циклу гиперграфа соответствует цикл в двойственном гиперграфе, то, применяя только что доказанный критерий к двойственному гиперграфу (разумеется, предварительно удалив изолированные вершины из исходного гиперграфа), получаем У т в е р ж д е н и е 68.3.
Гипергра$ Н не содержит циклов тогда и только тогда, когда для любого непустого подмножества т" <= т' выполняется неравенство () Г(с)!) Х (!8'(о)!-1). Приведем без доказательства (его можно найти в 120] )' еще один результат. Теорема 68.4 (Л. Ловас, 1968). !Если гиперграф Н порядка и не имеет циклов длины 1~3, а !е! > 2 и !е 0 е'! < 2 для любых различных е, е' сз е Н, то (! е ! — 2) ( и — )с (Н).
302 Циклическим рангом т(Н) гиперграфа Н называется циклический ранг его кенигова представления К(Н): т(Н) = т(К(Н)) = ~ !г) — ()Н!+ ~ЮН)) + к(К(Н)). гс М'И Из этого определения в силу следствия 13.5 вытекает, что гиперграф имеет единственный цикл тогда и только тогда, когда т(Н)= 1, т. е. когда ~~~Э ((в ~ — 1) = ив гнея — й(Н) + 1. Кроме того, очевидно, что т (Н*) = т (Н) . Наросочгтанигм в гиперграфе Н называется подмножество д" ':-д', для любых двух различных ребер г' и в" которого в' й г" = 8; таким образом, любые два ребра из 8' не смежны.
Паросочетание называется наибольшим, если число ребер в нем максимально среди всех паросочетаний в Н. Число ребер в наибольшем паросочетании гиперграфа Н называется числом паросочгтания и обозначается через ос~ (Н) . Пусть задано семейство Яи Ям ..., Я, непустых подмножеств конечного множества Я. Трансвврсальным мнозсгством этого семейства будем называть любое множество Т': — Я, такое что ТПЯ;Фо (г=1, к), Трансвврсальным множеством гипврграфа Н будем называть трансверсальное множество семейства его ребер. Таким образом, множество Т вЂ” ИН является трансверсальным множеством жшерграфа Н, если для любого ребра в — = д'Н справедливо соотношение Т П г Ф гг.
Очевидно, что в случае, когда о ' — наибольшее паросочетание в Н, множество () в является трапсверсальным ене множеством гнперграфа Н. Минимальное число вершин трансверсальпого множества называется числом грангвсрсальности гиперграфа Н и обозначается т(Н). Утверждение 685. Для любого гипгрграфа Н справедливо неравенство а1(Н) ( т(Н). > Если Р— паросочетание в гпперграфе Н, а Т— трапсверсальное множество этого гиперграфа, то ~Т( ) > ~Р~. Отсюда имеем т(Н)= ппп )Т)) шах )Р(=а„ таз н Раун где 0 Н вЂ” семейство всех трансверсальных множеств гиперграфа Н, УН вЂ” множество всех паросочетаний в Н.
г Число г(Н) = шах )в! называется рангом гипере сн графа Н. Утверждение 68.6. Длл любого гиперграфа Н т(Н) ~ г(Н) сс, (Н). > Пусть Рд ш ВН вЂ” наибольшее паросочетание. Тогда ~рг~ = и1(Н), а Ц е — трансверсальное множество нв' о гнперграфа Н. Поэтому т (Н) ( ! О в ( = ~ / е ! < г (Н) / Рг ! = г (Н) сс (Н). 5 69. Независимые множества Множество вершин гиперграфа называется независимым, если оно не содержит ребер.
Пустое множество вершин по определению независимо. Как и в случае графов, наибольшее по мощности независимое множество вершин гиперграфа Н называется наиболыиим, а число вершин в этом множестве называется числом независимости гиперграфа Н и обозначается через аг(Н). Через,7Н обозначается множество, элементами которого служат все независимые множества вершин гиперграфа Н.
Очевидно, что изучая независимые мно~кества вершин в гиперграфе, естественно рассматривать гиперграфы без кратных ребер. Опишем, как каждому такому гиперграфу поставить в соответствие монотонную булеву функцию. Пусть Н вЂ” гиперграф, РН = (т, 2, ..., п), хг =(хь хг, ..., х„) — характеристический вектор произвольного подмножества Н вЂ” )сН. Определим булеву функцию ~н, положив /„(х)= 0 для и-мерного (О, 1)-вектора х = хи тогда и только тогда, когда НАНН. Поскольку любое подмножество независимого множества также независимо, то функция )г монотонна и )л(0, О, ..., 0) = О. Соответствие Н ~н не является, вообще говоря, инъективным, поскольку ребра гиперграфа могут содержаться одно в другом.
Поэтому определенный интерес представляют гиперграфы специального вида — антицепи. Гиперграф называется антицгпью, если никакое из его ребер не является подмножеством другого ребра. Очевидно, что все Й-однородные гиперграфы и, в частности, все простые графы — антицепи. 304 Пусть Н вЂ” произвольная антицепь с непустым множеством ребер, Ъ'Н = (1, 2, ..., п). Очевидно, что характеристические векторы ребер гиперграфа Н попарно несравнимы относительно порядка <: х =(хь хь ..., х„) ~ < у =(уь ум ..., у ) еч (х; < уь (= 1, и). Поэтому существует единственная монотонная булева функция п переменных, множество нижних единиц которой совпадает с множеством всех характеристических векторов ребер гиперграфа Н.
Очевидно, что /л и есть такая функция. Для антицепи, не имеющей ребер, /и = — О. С другой стороны, пусть / — монотонная булеза функция и переменных, /ви 1. Определим гиперграф Нь положив )тН, = (1, 2, ..., п) и объявив ребрами все подмноя ества в )т//„характеристические векторы которых служат нижними единицами функции /.
Поскольку эта функция монотонна, то гиперграф Н, окажется антицепью. Очевидно, что /н~ — /. Итак, соответствие / Не — биекция между мновееством монотонных булевых функций, отличных от тождественно равной 1, и множеством антицепей. Пусть теперь А — произвольная т Х и-матрица без нулевых столбцов, элементы которой — ноотрицательные вещественные числа. Рассмотрим систему линейяых неравенств АХ<В. Здесь Х вЂ” столбец неизвестных хь хм ..., х,  — столбец высоты иг с неотрицательными элементами. Пас будут интересовать (О, 1)-решения атой системы.
Определим булеву функцию / п переменных, положив /(хь хм ..., х„) = О тогда и только тогда, когда (хп хь ..., х„)— решение системы (1). Очевидно, что / — монотонная функция и /(О, О, ..., О) = О. Скажем, что функция / задается системой неравенств (1). Легко понять, что любая монотонная булеза функция, отличная от тождественно равной 1, задается некоторой системой линейных неравенств вида (1) с неотрицательными коэффициентами и правыми частями. В самом деле, пусть / — такая функция, Н, — соответствующая антицепь, )тН, = (1, 2, ..., и), ЕН, = (еь ем ..., е„), ~е;1 = = и,(( = 1, т). Рассмотрим систему неравенств х, + х; + ...
+ х е и< — 1, ( = 1 лг. (2) Очевидно, что вектор х = хс =(хь хм ..., х ) — решение этой системы тогда и только тогда, когда (/~иУНо По- 20 в, л. кмеличев л лк. 305 следнее означает, что тнр — — О. Но )н = ~, следовательно, функция ) задается системой (2). Если же антицепь Нг не имеет ребер, т. е. если ) О, то в качестве системы неравенств (2) можно взять систему х; ~ 1 (г = 1, и) . Очевидно, что система неравенств, задающая монотонную булеву функцию, определяется неоднозначно. Из всего сказанного выше очевидно вытекает следующее У т в е р ж д е н и е 69.1.
Пусть 1 — монотонная булеза функция, отличная от тождественно равной 1, (1) — задающая эту функцию система линейных неравенств, Н,— соответствующая антицепь, УНг = (1, 2, ..., и), Н ы УНь яз — характеристический вектор подмножества Г Тогда следующие высказывания эквивалентны: 1) )(хо) = О; 2) вектор хо является решением системы (1); 3) П ен Нно Для того частного случая, когда все нижние единицы функции 1 имеют норму 2 (функция ) графическая), укаэанная связь между функциями, системами неравенств и антицепями отмечалась ранее в з 28. В этой и только в этой ситуации антицепь Н, является простым графом. В точности так же, как и для графов, определяется пороговое число 1Ь(Н) произвольной антицепи Н. Но в .общем случае этот важяый параметр изучался мало.
з 70. Раскраски Так жс, как для графов, вводится понятие вершинной раскраски гиперграфов. Раскраска вершин гкперграфа Н называется правильной, если любое ребро е ВН содержит две вершины, окрашенные в различные цвета. Ясно, что правильную раскраску могут допускать лишь гиперграфы, каждое ребро которых имеет степень не меньше чем 2. В этом параграфе рассматриваются только такие гиперграфы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
