Изменения

# Доказать или опровернгнуть: любое вершинное покрытие содержит как подмножество минимальное по мощности вершинное покрытие$k$-факторизацией графа называется разбиение множество ребер графа на его $k$-факторы.# Докажите, что $\alpha(G) \ge \fracK_4$ имеет единственную 1-факторизацию.# Найдите число $1$-факторизаций графа $K_6$.# Найдите число $1$-факторизаций графа $K_{n3,3}$.# Найдите число $1$-факторов графа $K_{1+\Delta(G)2n}$.# Докажите, что граф $\alpha(G) \ge \sum (1 + \deg u)^K_{6n-2}$ имеет 3-факторизацию.# Докажите, что граф $K_{4n+1}$имеет 4-факторизацию.# Как может поменяться Докажите, что граф $\alpha(G)K_9$ при удалении ребра? Удалении вершины? Добавлении ребра?представим в виде объединения 4 гамильтоновых циклов.# Верно лиПусть $G$ - регулярный граф степени $k$ с четным числом вершин, что для двудольного графа значение причем $\alphalambda(G)\ge k-1$ равно размеру максимальной доли?# Докажите, что . Пусть $G'$ получен из $ двудольный тогда и только тогда, когда для любого G$Hудалением не более чем $ k - подграфа 1$ ребер. Тогда $G'$ содержит совершенное паросочетание. Указание: используйте теорему Татта.# Пусть $G$ выполнено - регулярный граф степени $k$ с четным числом вершин, причем $\alphalambda(HG) \ge |VH|/2k-1$ (. Тогда для любого ребра $VHuv$ - множество вершин графа существует совершенное паросочетание, содержащее $Huv$).# Докажите, что если в дереве расстояние между двумя любыми листьями четно$G$ - регулярный граф четной степени, то в нем существует единственное максимальное по числу вершин независимое множествоу него есть 2-фактор. Верно ли обратное?# Зафиксируем Пусть $nr<k$ и хотя бы одно из них нечетно. Докажите, что существует $G$ - регулярный граф степени $k$. Рассмотрим граф, удовлетворяющий следующим условиям: (1) граф у которого нет $r$G-фактора.# Множество $ содержит S\subset V$n, для которого $ вершин; odd(G\setminus S)-|S|=def(2G) $\alpha, называется барьером. $A(G) \le k$является барьером графа. Среди таких графов рассмотрим граф с минимальным числом ребер. Этот граф называется граф Турана. ДокажитеПриведите пример графа, что в графе Турана любые две смежные вершины имеют равную степенькотором $A(G)$ не является максимальным по включению барьером.# Степень любых двух несмежных вершин Приведите пример графа, в графе Турана отличается не более чем на котором $1A(G)$не является минимальным по включению барьером.# ОценитеДокажите, сколько ребер в графе Тураначто пересечение двух максимальных по включению барьеров также является барьером.# Граф называется Пусть $x\alpha$-критическим, если удаление любого ребра увеличивает $in A(G)\alphacup C(G)$. Приведите пример , $G'=G\alphasetminus x$-критического и не , $\alphaB'$-критического барьер графа$G'$.# Докажите, что в любом дереве, кроме $K_2B=B'\cup x$ - барьер графа $G$ существует минимальное по числу вершин вершинное покрытие, включающее все вершины, соседние с листьями.# Доминирующим множеством в графе называется множество вершин, такое что каждая Следствие: любая вершина либо из $A(G) \cup C(G)$ входит в это множество, либо имеет соседа в этом множестве. Докажите, что независимое множество вершин является максимальным по включению если и только если оно является доминирующимбарьер графа $G$. # Обозначим размер минимального доминирующего множества в графе как Пусть $B$ - барьер графа $\gamma(G)$. Как связаны , тогда $B\alphacap D(G)$ пусто и все компоненты $\gammaD(G)$?# Докажите, что если в графе являются подмножествами нечетных компонент связности графа $G\setminus B$ нет изолированных вершин, и .# Пусть $AB$ - минимальное по включению доминирующее множество в барьер графа $G$, то существует причем $x \in B$, не имеющее общих вершин с . Тогда $AB' = B \setminus x$, также являющееся минимальным по включению доминирующим множеством в - барьер графа $G' = G \setminus x$.# Обозначим размер минимального Докажите, что пересечение всех максимальных по мощности вершинного покрытия множества в графе как включению барьеров $G$ равно $\betaA(G)$. Как связаны # Лапой называется индуцированный подграф $\gammaK_{1, 3}$ - вершина (Gцентр лапы)и три её соседа, не связанные между собой. Докажите, что если $ и B$ - минимальный по включению барьер $\beta(G)$?# Пусть , то каждая вершина $GB$ - связный кубический граф, в котором не более двух мостов. Тогда центр лапы в $G$ существует совершенное паросочетание.# Приведите пример связного кубического графаДокажите, содержащего три мостачто если связный граф $G$ содержит четное число вершин и не содержит лапы, в котором нет совершенного паросочетаниято он содержит совершенное паросочетание (Теорема Сумнера-Лас Вергнаса).