Полный подграф

Cтраница 2

Таким образом, выражение является выполнимым, если G содержит полный подграф с k вершинами. Обратно, если выражение является выполнимым, то существует распределение значений истинно и ложно по переменным, такое, что выражение истинно. Иначе говоря, каждый из k дизъюнктов содержит литерал, значение которого есть истинно, и вершины, соответствующие этим буквам, образуют полный подграф с k вершинами. Таким образом, граф G ( V, Е) содержит полный подграф с k вершинами, если и только если выражение является выполнимым. Очевидно, G можно построить по выражению за полиномиальное время. [16]

Матрицы инцидентностей мографов Sn, п З, яв. [17]

Тогда в графе пересечений Q ( 4r) мографа содержатся полные подграфы такие, - что пересечения слов, соответствующих их вершинам, пусты. [18]

Рассмотрим некоторое ( желательно близкое к наименьшему) покрытие графа полными подграфами. Граф полностью определится указанием этих полных подграфов и ребрами, которые соединяют вершины разных подграфов. Yn сопоставлено полным подграфам. [19]

Таким образом, задача нахождения всех решений головоломки эквивалентна нахождению всех полных подграфов из k вершин. [20]

Пусть Г - граф на v - 1 вершинах, в котором наибольшие полные подграфы ( клики) имеют объем k - 1 всякая вершина находится в К из них, и всякое р [ ебро лежит, по крайней мере, в одном из них. [21]

Полный подграф С графа G является максимумом клик графа G, если другой полный подграф G не содержит больше вершин, чем С. [22]

Опишем сначала простой недетерминированный полиномиальный алгоритм для определения того, содержит ли С полный подграф с k вершинами. Алгоритм недетерминированно выбирает подмножество из k вершин и проверяет за время 0 ( №), является ли оно полным. Теперь мы должны доказать, что задача является о - труд-ной; мы сделаем это, показав, что в нее преобразуется задача выполнимости. [23]

Наибольшим полным подграфом называется полный подграф, содержащий наибольшее число вершин среди всех полных подграфов данного графа. Число вершин наибольшего полного подграфа, содержащегося в данном графе, называется плотностью этого Графа. Плотность графа будем обозначать как f ( F) или / в тех случая х, когда будет ясно, о каком графе идет речь. [24]

РВ на X, а К пробегает все подмножества X, для которых К является полным подграфом. [25]

Требуется ответить на вопрос: содержится ли в графе Г, по крайней мере, один полный подграф со степенью, большей или равной / С. [26]

Теорема 9.3. Задача определения того, содержит ли неориентированный граф G ( V, E) полный подграф с k вершинами, является оЛГ - полной. [27]

Согласно определению У, это утверждение будет обосновано, если мы покажем, что множество У индуцирует полный подграф в графе G. Всякая вершина из У смежна по меньшей мере с k 1 вершинами из С, и поэтому любые две вершины из У имеют общего соседа в С. [28]

Граф и его граф клик. [29]

Теорема 2.8. Граф G является графом клик тогда и только тогда, когда он содержит семейство F полных подграфов, объединение которых дает G, таких, что если любая пара этих полных подграфов некоторого подсемейства F имеет непустое пересечение, то пересечение всех множеств из F также не пусто. [30]

Страницы: 1 2 3 4