Половина графика

Полуграф с 14 вершинами

В теории графов , разделе математики , полуграф — это особый тип двудольного графа . Эти графы называются полуграфами, потому что они имеют примерно половину ребер полного двудольного графа в одних и тех же вершинах. Название этим графикам дали Пол Эрдеш и Андраш Хайнал .

Определение

Чтобы определить полуграфик на $2n$ вершины $u_{1},\dots u_{n}$ и $v_{1},\dots v_{n}$, соединять $u_{i}$ к $v_{j}$ с краю всякий раз, когда $i\leq j$.

Эту же концепцию можно определить аналогичным образом для бесконечных графов над двумя копиями любого упорядоченного набора вершин. Полуграфик натуральных чисел (с их обычным порядком)обладает свойством, что каждая вершина $v_{j}$ имеет конечную степень , не более $j$. Вершины на другой стороне двудольного деления имеют бесконечную степень.

Характеристики

Расстояния

В полуграфе каждые две вершины находятся на расстоянии один, два или три. Любые две вершины $u_{i}$ и $u_{j}$ находятся на расстоянии два по пути через $v_{n}$, и любые две вершины $v_{i}$ и $v_{j}$ находятся на расстоянии два по пути через $u_{1}$. Если две вершины на противоположных сторонах двуразделения не являются соседними (на расстоянии один), то они находятся на расстоянии три через путь, проходящий через обе вершины. $u_{1}$ и $v_{n}$. Полуграфы являются частным случаем двудольных цепных графов (двудольных графов, в которых на каждой стороне двудольного деления вершины могут быть упорядочены путем включения окрестностей), которые, в свою очередь, являются частным случаем двудольных дистанционно-наследственных графов . Таким образом, полуграфы являются дистанционно-наследственными. То есть в каждом связном индуцированном подграфе полуграфа расстояния такие же, как и в самом полуграфе.

Соответствие

Половина графа имеет единственное совершенное паросочетание . Это легко увидеть по индукции: $u_{n}$ должен быть сопоставлен со своим единственным соседом, $v_{n}$, а оставшиеся вершины образуют еще одну половину графа. Более строго: каждый двудольный граф с уникальным совершенным паросочетанием является подграфом полуграфа.

В графах несчетного хроматического числа

Если хроматическое число графа несчетно ,тогда граф обязательно содержит в качестве подграфа половину графа натуральных чисел. Этот полуграф, в свою очередь, содержит каждый полный двудольный граф , в котором одна сторона двудольного деления конечна, а другая сторона счетно бесконечна.

Приложения

Регулярность

Одно из применений полуграфа встречается в лемме о регулярности Семереди :который гласит, что вершины любого графа можно разделить на постоянное количество подмножеств одинакового размера, так что большинство пар подмножеств являются регулярными.(ребра, соединяющие пару, ведут себя определенным образом как случайный граф определенной плотности). Если полуграф разбить таким образом на $k$ подмножеств, число неправильных пар будет по крайней мере пропорционально $k$. Поэтому невозможно усилить лемму о регулярности и показать существование разбиения, у которого все пары регулярны. С другой стороны, для любого целого числа $k$, графики, не имеющие $2k$-полуграф вершин как индуцированный подграф подчиняется более сильной версии леммы о регулярности без нерегулярных пар.

Стабильность

Сахарона Шела в Теорема о нестабильной формуле теории моделей характеризует стабильные теории ( полные теории , имеющие мало типов ) отсутствием счетных бесконечных полуграфов. Шелах определяет полную теорию как обладающую свойством порядка , если существует модель. $M$ теории, формула $\phi ({\bar {x}},{\bar {y}})$ на двух конечных наборах свободных переменных ${\bar {x}}$ и ${\bar {y}}$, и система счетного числа значений ${\bar {x}}_{i}$ и ${\bar {y}}_{i}$ для этих переменных такие, что пары ${\bigl \{}({\bar {x}}_{i},{\bar {y}}_{i})\mid M\models \phi ({\bar {x}}_{i},{\bar {y}}_{j}){\bigr \}}$ образуют ребра счетного полуграфа по вершинам ${\bar {x}}_{i}$ и ${\bar {y}}_{i}$. Интуитивно, существование этих полуграфов позволяет строить бесконечные упорядоченные множества внутри модели. Теорема о нестабильной формуле утверждает, что полная теория стабильна тогда и только тогда, когда она не обладает свойством порядка.

Вычислительная сложность

В форме гипотезы экспоненциального времени не существует управляемого алгоритма с фиксированным параметром для поиска полуграфа заданного размера в большем двудольном графе, будь то подграф или индуцированный подграф, когда он параметризован размером половины -граф.