Графы и орграфы

Начертите диаграмму каждого из следующих графов $G=(V, E)$:

Начертите диаграмму каждого из следующих графов $G=(V, E)$:

Определите простые графы среди графов из двух предыдущих задач. Если простой граф найден, определите, является ли он (i) двудольным графом, (ii) полным графом, (iii) полным двудольным графом или (iv) полным недвудольным графом.

Дополнением простого графа $G=(V, E)$ называется простой граф $\bar{G}=(V, F)$, в котором между двумя вершинами $\nu$ и $w$ существует ребро тогда и только тогда, когда между $\nu$ и $w$ нет ребра в $G$. Очевидно, что дополнение дополнения $\bar{G}$ есть $G$. Начертите диаграммы дополнений простых графов, найденных в задачах 1.1 и 1.2.

Покажите, что дополнение двудольного графа не обязано быть двудольным графом.

Начертите диаграмму ориентации простого недвудольного неполного графа, найденного в задачах 1.1 и 1.2.

Любая ориентация полного графа с множеством вершин $\left\{ 1,2, \ldots , n\right\}$ является турниром, и он называется транзитивным турниром, если для всех выборов $i, j$ и $k$ из наличия дуги из $i$ в $j$ и дуги из $j$ в $k$ следует наличие дуги из $i$ в $k$. Постройте как транзитивный турнир с четырьмя вершинами, так и турнир с четырьмя вершинами, не являющийся транзитивным.

Покажите, что каждый простой граф порядка $n$ изоморфен некоторому подграфу полного графа с $n$ вершинами.

Если два графа $G$ и $G^{\prime }$ изоморфны, то порядок $G$ равен порядку $G^{\prime }$, а размер $G$ равен размеру $G^{\prime }$.

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

Покажите, что два простых графа изоморфны тогда и только тогда, когда изоморфны их дополнения.

Определите, изоморфны ли три графа, изображённые на Fig. 1-10.

Fig. 1-10

Пусть $N(n, k)$ — число неизоморфных простых графов с $n$ вершинами и $k$ рёбрами. Найдите $N(4,3)$.

Найдите все неизоморфные простые графы порядка 4.

Простой граф, изоморфный своему дополнению, называется самодополнительным графом. Найдите самодополнительный граф порядка 4.

Найдите два самодополнительных графа порядка 5.

Найдите вершинно-порождённый двудольный подграф графа на Fig. 1-6(a).

Множество $I$ вершин простого графа $G=(V, E)$ называется независимым множеством (также известным как внутренне устойчивое множество) в $G$, если никакие две вершины из $I$ не смежны. Множество $K$ вершин графа $G$ называется вершинным покрытием, если каждое ребро графа инцидентно хотя бы одной вершине из $K$. Покажите, что множество вершин $K$ является вершинным покрытием тогда и только тогда, когда его дополнение $(V-K)$ является независимым множеством.

Независимое множество $I$ в простом графе $G$ называется наибольшим независимым множеством, если в $G$ не существует независимого множества $I^{\prime }$ такого, что $\left|I^{\prime }\right|>\left|I\right|$. Число вершин в наибольшем независимом множестве графа $G$ называется числом независимости $\alpha (G)$ (также известным как число внутренней устойчивости) графа $G$. Вершинное покрытие $K$ графа $G$ называется наименьшим вершинным покрытием, если не существует вершинного покрытия $K^{\prime }$ такого, что $\left|K^{\prime }\right|<\left|K\right|$. Число вершин в наименьшем вершинном покрытии называется числом вершинного покрытия $\beta (G)$ графа $G$. Найдите число вершинного покрытия и число независимости графа на Fig. 1-14.

Fig. 1-14

Покажите, что для простого графа $G$ порядка $n$ выполняется $\alpha (G)+\beta (G)=n$.

Подмножество $D$ вершин простого графа $G$ называется доминирующим множеством вершин (также известным как внешне доминирующее множество), если каждая вершина, не принадлежащая $D$, смежна хотя бы с одной вершиной из $D$. Найдите:

Доминирующее множество вершин $D$ называется наименьшим доминирующим множеством вершин, если не существует доминирующего множества $D^{\prime }$ такого, что $\left|D^{\prime }\right|<\left|D\right|$. Число вершин в наименьшем доминирующем множестве вершин называется числом доминирования вершин $\sigma (G)$ (также известным как число внешней устойчивости) графа. Покажите, что число доминирования вершин простого графа не может превышать его числа независимости.

Независимое множество называется максимальным независимым множеством, если оно не является собственным подмножеством другого независимого множества. Покажите, что независимое множество является доминирующим множеством вершин тогда и только тогда, когда оно является максимальным независимым множеством. (Максимальное независимое множество — не то же самое, что наибольшее независимое множество, определённое в задаче 1.19.)

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

Комитет $S$, описанный в задаче 1.24, называется наименьшим комитетом, если не существует комитета $S^{\prime }$ такого, что $\left|S^{\prime }\right|<\left|S\right|$. Числом комитета множества называется мощность наименьшего комитета этого множества. Найдите число комитета графа знакомств на Fig. 1-14.

Множество $M$ рёбер графа называется паросочетанием (также известным как независимое множество рёбер), если никакие два ребра из $M$ не имеют общей вершины. Множество рёбер $L$ называется рёберным покрытием, если каждая вершина положительной степени является вершиной хотя бы одного ребра из $L$. Покажите, что дополнение паросочетания не обязано быть рёберным покрытием. (Сравните этот результат с результатом задачи 1.18.)

Паросочетание $M$ в простом графе называется наибольшим паросочетанием (также известным как паросочетание наибольшей мощности), если не существует паросочетания $M^{\prime }$ такого, что $\left|M^{\prime }\right|>\left|M\right|$. Число рёберной независимости $\alpha_{1}(G)$ графа $G$ — это число рёбер в наибольшем паросочетании. Рёберное покрытие $L$ простого графа $G$ называется наименьшим рёберным покрытием, если не существует рёберного покрытия $L^{\prime }$ графа $G$ такого, что $\left|L^{\prime }\right|<\left|L\right|$. Число рёберного покрытия $\beta_{1}(G)$ графа равно сумме числа рёбер в наименьшем рёберном покрытии и числа изолированных вершин. Найдите число рёберной независимости и число рёберного покрытия графа на Fig. 1-14.

Покажите, что для простого графа $\alpha_{1}+\beta_{1}=n$.

Множество $F$ рёбер графа $G=(V, E)$ называется доминирующим множеством рёбер, если каждое ребро, не входящее в $F$, имеет общую вершину с некоторым ребром из $F$. Число рёберного доминирования $\sigma_{1}(G)$ — это число рёбер в наименьшем доминирующем множестве рёбер. Найдите число рёберного доминирования графа на Fig. 1-14.

Покажите, что число рёберного доминирования не может превышать число рёберной независимости.

Найдите необходимое и достаточное условие, которому должно удовлетворять паросочетание, чтобы быть доминирующим множеством рёбер.

Найдите число рёбер в полном графе с $n$ вершинами.

Используя методы теории графов, покажите, что $1+2+\cdots +n=n(n+1) / 2$.

Покажите, что число вершин самодополнительного графа равно либо $4 k$, либо $4 k+1$, где $k$ — положительное целое число.

Найдите число рёбер полного двудольного графа $K_{m, n}$.

Докажите теорему 1.1: сумма степеней графа вдвое больше числа его рёбер.

Используя теорему 1.1, найдите размер $K_{n}$ и $K_{m, n}$.

Докажите теорему 1.2: каждый граф имеет чётное число нечётных вершин.

Постройте два неизоморфных простых графа с шестью вершинами степеней $1,1,2,2,3$ и 3. Найдите размер построенного таким образом графа.

Покажите, что если $G$ и $G^{\prime }$ — изоморфные графы, то степень каждой вершины сохраняется при изоморфизме.

Покажите, что два графа $G$ и $G^{\prime }$ с одним и тем же множеством вершин $V=\left\{ 1,2, \ldots , n\right\}$, у которых степень вершины $i$ одинакова для обоих графов при каждом $i$, не обязаны быть изоморфными.

Докажите теорему 1.3: в орграфе сумма полустепеней исхода всех вершин равна числу дуг, что также равно сумме полустепеней захода всех вершин.

Покажите, что не существует простого графа с 12 вершинами и 28 рёбрами, в котором $(i)$ степень каждой вершины равна либо 3, либо 4, и (ii) степень каждой вершины равна либо 3, либо 6.

Покажите, что не существует простого графа с четырьмя вершинами, у которого три вершины имеют степень 3, а одна вершина — степень 1.

Помеченный граф с $\boldsymbol {n}$ вершинами получается путём присвоения меток $1,2, \ldots , n$ вершинам данного графа $G$ с $n$ вершинами и $m$ рёбрами. Два помеченных графа, полученных таким образом из данного графа $G$, обязательно изоморфны, но не обязательно тождественны. Пометьте вершины простого графа с четырьмя вершинами степеней $1,1,1$ и 3, построив три изоморфных графа $G_{1}, G_{2}$ и $G_{3}$ таких, что (i) $G_{1}$ и $G_{2}$ тождественны, и (ii) $G_{1}$ и $G_{3}$ не тождественны.

Найдите число нетождественных помеченных графов с $n$ вершинами.

Покажите, что число вершин $k$-регулярного графа чётно, если $k$ нечётно.

Покажите, что не может существовать группа из семи человек, в которой каждый человек знаком ровно с тремя другими членами группы.

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

Положительное целое число $n$ обладает $(\boldsymbol {p}, \boldsymbol {q})$-свойством Рамсея, если для каждого графа $G$ с $n$ вершинами либо $K_{p}$ является подграфом $G$, либо $K_{q}$ является подграфом дополнения $G$. Покажите, что положительное целое число 6 обладает $(3,3)$-свойством Рамсея, тогда как число 5 им не обладает.

Покажите, что следующие свойства эквивалентны: (i) положительное целое число $n$ обладает $(p, q)$-свойством Рамсея, (ii) каждый простой граф с $n$ вершинами содержит клику из $p$ вершин или независимое множество из $q$ вершин, и (iii) рёбра $K_{n}$ можно раскрасить двумя цветами так, что найдётся либо клика $K_{p}$, все рёбра которой одного цвета, либо клика $K_{q}$, все рёбра которой другого цвета.

Наименьшее целое число $n$, обладающее $(p, q)$-свойством Рамсея, называется числом Рамсея и обозначается $\boldsymbol {R}(\boldsymbol {p}, \boldsymbol {q})$. Покажите, что:

Покажите, что если двудольный граф $G=(X, Y, E)$ регулярен, то $X$ и $Y$ содержат одинаковое число элементов.

Кубическим графом называется простой граф, в котором степень каждой вершины равна 3. Постройте два неизоморфных кубических графа, каждый из которых имеет шесть вершин.

Найдите наибольшее число рёбер в двудольном графе.

$\boldsymbol {k}$-кубом (также известным как гиперкуб) называется граф $Q_{k}$, вершинами которого являются упорядоченные $k$-наборы двоичных чисел, причём две вершины соединены ребром тогда и только тогда, когда они отличаются ровно в одной компоненте. Покажите, что $k$-куб является $k$-регулярным двудольным графом, и найдите число вершин и рёбер $k$-куба.

Найдите наименьшее число вершин, необходимое для построения полного графа не менее чем с 1000 рёбрами.

Покажите, что вершины двудольного графа $G=(X, Y, E)$ с $m$ вершинами в $X$ и $n$ вершинами в $Y$ можно занумеровать так, что матрица смежности примет вид

где $A$ — матрица размера $m \times n$, каждый элемент которой равен 0 или 1, $A^{T}$ — транспонированная матрица $A$, а 0 — матрица, все элементы которой равны нулю.

Докажите теорему 1.4: (i) В матрице смежности графа сумма элементов строки (или столбца), соответствующей вершине, равна её степени, а сумма всех элементов матрицы вдвое больше числа рёбер графа. (ii) В матрице смежности орграфа сумма элементов строки, соответствующей вершине, равна её полустепени исхода, сумма элементов столбца, соответствующей вершине, равна её полустепени захода, а сумма всех элементов матрицы равна числу дуг орграфа.

Докажите теорему 1.5: (i) Сумма элементов строки матрицы инцидентности простого графа, соответствующей вершине, равна её степени, а сумма всех элементов матрицы вдвое больше числа рёбер. (ii) Сумма элементов строки матрицы инцидентности орграфа равна разности между её полустепенью исхода и полустепенью захода, а сумма всех элементов матрицы равна нулю.

Матрицей перестановки называется квадратная бинарная матрица, имеющая ровно одну единицу в каждой строке и в каждом столбце. Две матрицы $A$ и $A^{\prime }$ называются изоморфными, если существует такая матрица перестановки $P$, что $A^{\prime } P=P A$. Покажите, что два графа изоморфны тогда и только тогда, когда изоморфны их матрицы смежности.

Найдите матрицы смежности $A$ и $A^{\prime }$ двух изоморфных графов, изображённых на Fig. 1-18, и найдите матрицу перестановки $P$ такую, что $A^{\prime } P=P A$.

Fig. 1-18

Характеристическим многочленом простого графа с $n$ вершинами называется определитель матрицы $(A-\lambda I)$, где $A$ — матрица смежности, а $I$ — единичная матрица размера $n \times n$. Покажите, что если два графа изоморфны, их характеристические многочлены совпадают. (Замечание: определитель $A$ записывается как $\operatorname {det} A$.)

Вычислив характеристические многочлены двух графов, показанных на Fig. 1-19, покажите, что два неизоморфных графа могут иметь одинаковый характеристический многочлен.

Fig. 1-19

Если $A=\left[a_{i j}\right]$ — матрица смежности простого графа $G$ с $n$ вершинами, двоичным кодом $G$ относительно $\boldsymbol {A}$ называется неотрицательное целое число $a_{12} 2^{0}+a_{13} 2^{1}+\cdots +a_{1 n} 2^{n-1}+a_{23} 2^{n}+\cdots +a_{2 n} 2^{2 n-3}+ \cdots +a_{n-1, n} 2^{k-1}$, где $k=n(n-1) / 2$. Найдите двоичный код матрицы смежности графа $G=(V, E)$, где $V=\left\{ 1,2,3,4\right\}$ и $E=\left\{ \left\{ 1,2\right\} ,\left\{ 1,4\right\} ,\left\{ 2,4\right\} ,\left\{ 3,4\right\} \right\}$.

Покажите, что можно построить простой граф $G$, если известны двоичный код одной из его матриц смежности и порядок $G$.

Минимальным кодом графа называется его наименьший двоичный код, а наибольший двоичный код называется максимальным кодом графа. Найдите минимальный и максимальный коды простого графа с тремя вершинами и двумя рёбрами.

Докажите теорему 1.6: Пусть $v=\left[\begin{array}{lllll}d_{1} & d_{2} & d_{3} & \cdots & d_{k}\end{array}\right]$ — невозрастающий вектор из $k$ (где $k$ не меньше 2) неотрицательных целых чисел, в котором ни одна компонента $d_{i}$ не превосходит $(k-1)$. Пусть $v^{\prime }$ — вектор, полученный из $v$ удалением $d_{1}$ и вычитанием 1 из каждой из следующих $d_{1}$ компонент $v$. Пусть $v_{1}$ — невозрастающий вектор, полученный из $v^{\prime }$ перестановкой его компонент, если это необходимо. Тогда $v$ является графическим вектором тогда и только тогда, когда $v_{1}$ является графическим вектором.

Докажите, что алгоритм из раздела 1.6 определяет, является ли заданный вектор неотрицательных целых чисел графическим вектором.

Проверьте, является ли $\left[\begin{array}{llllllll}5 & 4 & 3 & 3 & 3 & 3 & 3 & 2\end{array}\right]$ графическим вектором. Если он графический, начертите простой граф, для которого этот вектор является вектором степеней.

Проверьте, является ли $\left[\begin{array}{lllllll}6 & 6 & 5 & 4 & 3 & 3 & 1\end{array}\right]$ графическим вектором.

Пусть $v=\left[\begin{array}{llll}d_{1} & d_{2} & \cdots & d_{n}\end{array}\right]$ и $w=\left[\begin{array}{lllll}w_{n} & w_{n-1} & \cdots & w_{2} & w_{1}\end{array}\right]$, где $w_{i}=n-1-d_{i}$. Покажите, что $v$ графический тогда и только тогда, когда $w$ графический.

Покажите, что не существует простого графа с шестью вершинами, у которого степени пяти вершин равны $5,5,3,2$ и 1.

Найдите $x$, если $\left[\begin{array}{llllllllllll}8 & x & 7 & 6 & 6 & 5 & 4 & 3 & 3 & 1 & 1 & 1\end{array}\right]$ — графический вектор.

Покажите, что конечный невозрастающий вектор, никакие две компоненты которого не равны между собой, не может быть графическим вектором.

Покажите, что в простом графе найдутся по крайней мере две вершины с одинаковыми степенями.

Покажите, что существует простой граф с 12 вершинами и 28 рёбрами, в котором степень каждой вершины равна либо 3, либо 5. Начертите этот граф.

Покажите, что существует простой граф с семью вершинами и 12 рёбрами, в котором степень каждой вершины равна 2, 3 или 4.

Найдите дополнения:

Найдите число неизоморфных графов с четырьмя вершинами и не более чем 3 рёбрами.

Найдите число вершинного покрытия и число независимости графов $K_{n}$ и $K_{m, n}$.

Найдите число доминирования вершин графов $K_{n}$ и $K_{m, n}$.

Найдите число комитета:

Если $I$ — независимое множество в графе, найдите подграф, порождённый $I$.

Найдите наибольшее число рёбер в

Известно, что существует простой граф с 12 вершинами и 28 рёбрами, в котором степень каждой вершины равна либо 3, либо 5. Найдите число вершин степени 3.

Найдите число нетождественных графов с четырьмя вершинами и тремя рёбрами.

Найдите число нетождественных графов с пятью вершинами и тремя рёбрами.

Если $G$ — $k$-регулярный граф с $n$ вершинами, найдите число треугольников в $G$ и в его дополнении.

Покажите, что если каждое ребро графа соединяет нечётную вершину с чётной, то граф является двудольным. Верно ли обратное?

Любой корень характеристического многочлена графа называется собственным значением графа. Спектром графа называется совокупность всех его собственных значений. Найдите спектр:

Найдите минимальный и максимальный коды простого графа с четырьмя вершинами, степени вершин которого равны $1,2,2$ и 3.

Найдите минимальный и максимальный коды графа $K_{n}$.