Номер пересечения (теория графов)
В математической области теории графов число пересечений графа G = ( V , E ) — это наименьшее количество элементов в представлении G как графа пересечений конечных множеств . Эквивалентно, это наименьшее количество клик , необходимое для покрытия всех ребер G . [1] [2]
Пусть F — семейство множеств (допускающее повторение множеств в F ); тогда граф пересечений F является неориентированным графом , имеющим вершину для каждого члена F и ребро между каждыми двумя элементами, имеющими непустое пересечение. Таким образом любой граф можно представить в виде графа пересечений. [3] Числом пересечения графа называется наименьшее число k такое, что существует представление этого типа, для которого объединение F имеет k элементов. [1]Задача нахождения представления пересечения графа с заданным числом элементов известна как задача базиса графа пересечений . [4]
Альтернативное определение числа пересечений графа G состоит в том, что это наименьшее количество клик в G ( полных подграфов G ) , которые вместе покрывают все ребра G. [1] [5] Набор клик с этим свойством известен как покрытие ребра клики или покрытие ребра клики , и по этой причине число пересечения также иногда называют числом покрытия ребра клики . [6]
Равенство числа пересечений и числа покрытия реберной кликой доказывается просто. В одном направлении предположим, что G является графом пересечений семейства множеств F , объединение которых U состоит из k элементов. Тогда для любого элемента x из U подмножество вершин G , соответствующих множествам, содержащим x , образует клику: любые две вершины в этом подмножестве являются смежными, поскольку их множества имеют непустое пересечение, содержащее x . Далее, каждое ребро в Gсодержится в одной из этих клик, поскольку ребро соответствует непустому пересечению, а пересечение непусто, если оно содержит хотя бы один элемент из U . Следовательно, ребра G можно покрыть k кликами, по одной на элемент U . С другой стороны, если граф G может быть покрыт k кликами, то каждая вершина графа G может быть представлена набором клик, содержащих эту вершину. [5]
Тривиально граф с m ребрами имеет число пересечений не более m , так как каждое ребро образует клику, и эти клики вместе покрывают все ребра. [7]
Также верно, что каждый граф с n вершинами имеет число пересечений не более n 2 /4 . Более того, ребра каждого n -вершинного графа можно разделить не более чем на n 2 /4 клик, все из которых являются либо одиночными ребрами, либо треугольниками. [2] [5] Это обобщает теорему Мантеля о том , что граф без треугольников имеет не более n 2/4 ребер , поскольку в графе без треугольников единственное оптимальное кликовое реберное покрытие имеет по одной клике на ребро, и, следовательно, число пересечений равно количество ребер. [2]
