В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 41
Текст из файла (страница 41)
224 ь Пусть 6 — пороговый граф порядка п, (1) — разделяющее неравенство. Рассмотрим граф К ° 6. Пусть а— минимальное число среди коэффициентов ав в неравенстве (1); Ь вЂ” минимальное число среди всех таких сумм К=и!х!+ягхг+...+се„х, х;=О, 1~ 1= 1, п~ что Я - р; 6 и 1 — произвольные числа, удовлетворяющие поравепствам 6<6<Ь, 6 — а<1<6. (2) (В случае, когда 6 = О„, указанного Ь не существует и в (2) соответствующее неравенство опускается.) Прямая проверка подтвернвдает, что неравенство а~х~ + агхг +... + а„х„+ 1х„ы < 6 (3) является разделягощим для графа К ° 6.
Аналогично, взяв в (3) 1 и 6, удовлетворяющие условиям р < 6 < Ь, 1 < 6 — р, получим разделяющее неравенство для графа 0 ° 6. ч Как отмечалось выше, некоторые графы являются упиграфами, т. е. с точностью до изоморфизма определяются своими степенными последовательностями. Из того факта, что лгобые две реализации графической последовательности получаются одна пз другой с помощью цепочки переключений (теорема 65т!), вытекает Следствие 50.5. Граф 6 является униграфом тогда и только тогда, когда для любого переключения з графы 6 и з6 изоморфны. Нинге доказано, что пороговые графы и только опи составляют простейший класс Л' униграфов — графов, вовсе пе допускающих переключений, отличных от тождественного.
Непосредственно из определения переключения вытекает следующая характеризацин этого класса в терминах запрещенных порожденных подграфов. Утверждение 50.6, Граф принадлежит классу Л' тогда и только тогда, когда ни один иг трех графов 2Кг, Р4 и С4 не является его порожденным подграфом. Следствие 50.3 означает, что лгобой пороговый граф принадлежит классу Л. Лемма 50.7. Если 6 ~Л', то в графе 6 есть либо доминирующая, либо изолированная веригина.
> Пусть, напротив, 6~Ле и в графе 6 нет ни доминирующих, пп изолированных воршпп, и пусть н — его вершина максимальной степени. Тогда в этом графе существуют две такие вершины о и ш, что ио ж Е6, ишФЕ6. 15 в. л. вмеввчев и вэ. 225 Гслн нри атом ой я ЕС, то, поскольку степень вершины и максимальна, существует четвертая вершина х, смежная с и н не смежная с о (см. рнс. 50.3). Пороягденный нодграф С (и, о, и, х) входят в сансов нодграфов, запрещенных для класса Л' утверждением 50.6 (он совнадаот с Р4 нлн с С4). Пусть ойФЕ6.
Так как в графе С нот изолированных верпшн, то существует чотвертан вершина х, смежная с й. Першины и н о смежны с х, иначе порожденный у у Рнс. 50.4 Рис. 50,3 водграф С(и, о, й, х) имел бы внд, занрещснный утверждонием 50.6. Так как и — вершнна максимальной степени, то существует пятая вершина у, смежная с и, но но смежная с х. Подграф 6(и, й, х, у) снова занрощенньш (рнс. о0.4). Полученное нротнворечие доказывает лемму. < Очевидны следующие два свойства графов нз класса Л'. 1, Порождензый подграф любого графа из класса Л' также принадлежит этому классу. 2. Если С шУ, то оба графа К ° С и О ° 6 также принадлежат классу Л'.
Для п ) 2 ноложнм С! ' 62 ° ° ° ' 6» = С~ (62 ( ° ° 6») )1 где 6 =Кь С,=К илн 6~= 0 (1= 1, п — 1). Очевпдяо, что из вышесказанного вытекает следующее Утвержден не 50.8. Класс Л' есть класс всех графов, имеюи1их вид С! ° 62 ... С., где С„= Ки п > 1, а для 1= 1, п — 1 компоненты С, независимо друг от друга принимают значения К или О. Т е о р е м а 50.9. Граф является пороговым тогда и только тогда, когда ои имеет вид, описашгый в утверждении 50.8. 1> Требуется доказать, что класс пороговых графов совпадает с классом Л'. Былие отмечалось, что любой пороговый граф принадлежит классу Л.
С другой стороны, 226 согласно утверждению 50.8 любой граф из класса М можно построить, исходя из одной вершины, присоединяя на каждом шаге к уже полученному графу либо доминирующую, либо изолированную вершину. Одновершпнпьш граф является пороговым. Согласно лемма 50.4 свойство пороговости графа сохраняется при присоединении к графу новой доминирующей илп изолированной вершины. Следовательно, любой граф пз класса Л' являетсн пороговым.
ч Следствие 50 10. Любой пороговый граф является раси!епляемыл. с' Пусть пороговый граф С получается из вершины а в результате присоединения на каждом шаге к уже полученному графу либо домиппрувоптей, либо изолированной Рвс. 50.5 вершины. Отнеся к верхней доле верпшпу а и все вершипы, присоединенные как домнпиру|ощне, а к ппжпей доле — все остальные верппшьт, получим полярное разбпопие множества ИС.
Следовательно, граф 6 расщепляем. <! Следствие 50.11. Для любого натурального числа п суи!ествует ровно 2" ' попарно иеизоморфиых пороговых ерафов порядка и. с> Очевидно, что два графа 6, ° Сг °... ° 6„, 6, ° 6, ° ... ° С вида, описанного в утверя"дании 50.8, изоморфны тогда и только тогда, когда и = тп, С; = С;, 1 = 1, п — 1. Каждая из компонент 6, может принимать два значения.
Следовательно, число пеизоморфных среди таких графов равно 2" '. < Па рис. 50.5 показаны все 8 пороговых графов порядка 4. Из теоремы 50.9 слодует, что каждый пз ппх определяется (О, 1)-вектором (сс, р, 7). Пепосредствеппо иа теоремы 50.9 вытекает Следствие 50.12. Если С вЂ” пороговый граф, то и дополнительный граф С галлее является порововым.
227 15в Графическая последовательпостгч имеющая пороговую реализацию, называется пороговой. Все реализации пороговой последовательности изоморфны, поскольку пороговый граф является уннграфом. Очевидно, что из теоремы 50.9 вытекает следующий критерий пороговости последовательности целых неотрицательных чисел. Следствие 50.13. При и ) 1 правильная и-последовательность а' является пороговой тогда и только тогда, когда верно одно из следующих двух утверхсдений: 1) 4 = и — 1 и производная последователыгость гР = =(йг — 1, ..., с( — 1) пороговая; 2) и„= 0 и производная последовательность й" = =(дь йг, ..., И„~) пороговая. э 51. Пороговое разложение графа Поскольку граф с одним ребром является пороговым, то любой граф 6 можно представить в виде объединения 6=6 06 0...06 пороговых графов 6; с совпадающими множествами вершин.
Пазовем такое представление пороговым раглогкением графа 6. Минимальное число С компонент в пороговых разложениях графа 6 назовем пороговым числом графа 6 и обозначим через $5(6). Параметр СЬ(6) связан с минимизацией числа липейпых неравенств, задающих булеву функцию. Рассмотрим эту связь. Пусть сгнх~+ иггхг+...
+иых ~ ~н геенах~ + сгггхг+... +Сгг„х ~ тг, анх, + амхг+... +и,.х ~ р, — система линейных неравенств с веществеппгями коэффициентами и правыми частями, В = (О, 1), В" — мпогкество всех бинарных векторов (хн хг, ..., х„) длины и. Определим булеву функцию ~: В"- В, положив ~(хи хг, ... ..., х„)= 0 тогда и только тогда, когда вектор (х~, хг, ... ..., х„) удовлетворяет системе (1). Будем говорить, что функция С' определяется системой неравенств (1). Тем самым множество нулей булевой функции, определяемой системой линейных неравенств, совпадает с множеством (О, 1)-решений этой системы. 228 Теорема 511. Л!обпя булеза 4унк2/ия определяется некоторой системой линейных нераоенств.
1> Известно, что всякая булеза функция / от и переменных может быть задана своей совершенной дигъюнктивной нормальной формой (совершенной д. н. ф.): а1 а2 аа /(Х1' Х22 ' ' '~ ха) Ч х1 хг ' хп 1 где (о!, ог, ..., о„) пробегает мно1кество всех единиц функции /, (х! при о;=1, (х! при о! = 0 (см., например, [32) ). Легко видеть, что кан!дая конъюнкция д вида а1 а2 аа а(Х1~Х22'''~ха)Х1'12'Ха определяется одним линейным неравенством. В самом деле,пусть, длн определенности, д(х1, хг, ..., х„) =х!хг...х„. рассмотрим неравенство х! + Хг +... + х„~~ и — 1.
Г>ипарньш вектор х =(х!, хг, ..., х„) пе удовлетворяет этому неравенству только при условиях х! = хг =... = х„= 1. Но эти же условия необходимы и достаточны длн того, чтобы вектор х был единицей функции /. Аналогично, копь!онкцин Х!... ХАХ11-!... Ха определнетсн неравенством х! +...+ х„— х,„! —... — х„~ й — 1. Итак, кан!дан элементарнан конъюнкции, входящая в совершенную д.
п. ф. функции /, определяется одним липойпым неравенством. Очевидно, что функция / определпетсн системой этих неравенств. с1 Минимальное число 1 неравенств в системах, зада!ощих фупкци!о /, наэываетсн пороговым числом функции / и обозпачаетсн через ~(/). Гели функция / графическан, т. е. /= =О или / — мопотоннан булева функция, все нижние единицы которой имеют норму 2, то, как показано в 229 $28, этой функции соответствует граф Сп множество характеристических векторов независимых подмножеств вершин которого совпадает с множеством нулей функции 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
