Полный подграф
Cтраница 1
Полный подграф С графа G является максимумом клик графа G, если другой полный подграф G не содержит больше вершин, чем С. [1]
Наибольшим полным подграфом называется полный подграф, содержащий наибольшее число вершин среди всех полных подграфов данного графа. Число вершин наибольшего полного подграфа, содержащегося в данном графе, называется плотностью этого Графа. Плотность графа будем обозначать как f ( F) или / в тех случая х, когда будет ясно, о каком графе идет речь. [2]
 |
Ориентированный граф ( а и неориентированный граф ( b, u которых гамильтоновы циклы показаны жирной линией. ( с - неориентированный граф, не имеющий гамильтоновых циклов. [3] |
Двойственность полных подграфов графа и вершинных покрытий его дополнения позволяет тривиально доказать следующие результаты. [4]
Если Г0 - полный подграф б - графа Г, состоящий из целых клеток ( и снабженный прежними метками), то Р0 - также РН - граф. [5]
Наибольшим полным подграфом называется полный подграф, содержащий наибольшее число вершин среди всех полных подграфов данного графа. Число вершин наибольшего полного подграфа, содержащегося в данном графе, называется плотностью этого Графа. Плотность графа будем обозначать как f ( F) или / в тех случая х, когда будет ясно, о каком графе идет речь. [6]
Перед началом работы уутт - Если полный подграф степени у найден и г / т / тах, то найденный подграф образует текущий массив R, значение переменной у увеличивается на единицу и работа алгоритма продолжается. Если при некотором значении у получено, что полного подграфа такой степени в исследуемом графе не содержится, то fy - 1, а подграф, найденный при предыдущем значении у, есть наибольший подграф. [7]
 |
Первые три графа Муна - Мозера. [8] |
Каждый узел в дереве поиска соответствует полному подграфу графа, и каждое ребро соответствует вершине графа. Сын данного узла С получается добавлением к С вершины х С, которая смежна с каждой вершиной из С. На рис. 8.17 показаны некоторый граф G и дерево поиска Т, которое проходится в процессе естественного поиска с возвращением. [9]
Если и0, то счет окончен: полного подграфа степени / С в графе Г не существует. [10]
В работах [28, 29] описаны оригинальные алгоритмы поиска максимальных пустых и полных подграфов. Некоторые из алгоритмов имеют приближенный характер. [11]
В заданном графе найти максимальный по количеству вершин полный подграф. [12]
Преобразуем вопрос о его выполнимости в вопрос существования полного подграфа с k вершинами в графе, который можно построить из данного выражения за время, полиномиальное относительно его длины. [13]
При каких условиях ребра реберного графа можно разбить на полные подграфы таким образом, чтобы каждая вершина принадлежала в точности двум из подграфов. [14]
Для произвольного графа G существует граф пересечений, определяемый только полными подграфами графа G. [15]
Страницы: 1 2 3 4