Graphiques à séparation minimale

Question

Nous disons qu'un graphique simple et non orienté $G=(V,E)$on sépare si pour tout$x\neq y\in V$ il y a $e_x,e_y\in E$ tel que $x\in e_x$ et $y\in e_y$, et $e_x\cap e_y = \varnothing$. Nous disons$G$se sépare au minimum si elle sépare et pour tous$E'\subseteq E$ avec $E'\neq E$ nous avons ça $(V,E')$ ne sépare plus.

Voici un exemple: considérons une union disjointe infinie de carrés; formellement, définir$V=\omega$, et laissez $$E = \big\{\{n,n+1\}: (n\in\omega) \land(\forall a\in \omega(4a+3 \neq n))\big\}\cup\big\{\{4n,4n+3\}:n\in \omega\big\}.$$ ensuite $G=(V,E)$ est une séparation minimale.

Question. Si$G=(V,E)$ est un graphe de séparation, y a-t-il $E_1\subseteq E$ tel que $(V,E_1)$ est la séparation minimale?

Answer 1

Oui, chaque graphe de séparation a un sous-graphe couvrant qui sépare au minimum. La preuve utilise la même idée que le théorème de Banakh – Petrov .

Laisser $G=(V,E)$être un graphe de séparation. j'écrirai$N(x)$ et $d(x)=|N(x)|$ pour le voisinage et le degré d'un sommet $x$ dans $G$et j'écrirai $N_1(x)$ et $d_1(x)$ pour le quartier et le degré de $x$ dans le sous-graphe couvrant $G_1=(V,E_1)$ à construire à l'étape 1.

Étape 1. Laissez$G_1=(V,E_1)$ être un sous-graphe couvrant maximal de $G$ avec degré maximum $\Delta(G_1)\le3$, et laissez $W=\{x\in V:d_1(x)=3\}$; donc chaque bord$e\in E\setminus E_1$ a au moins un point de terminaison dans $W$.

Étape 2. Nous allons maintenant construire un ensemble$E_2\subseteq E\setminus E_1$ tel que $G_{1,2}=(V,E_1\cup E_2)$ est un graphe de séparation, et $G_{1,2}-e$ est non séparateur pour chaque $e\in E_2$. Dans le but de faire$G_1$ un graphe de séparation en ajoutant de nouvelles arêtes, nous n'avons qu'à nous soucier des sommets $x$ tel que soit $d_1(x)\lt2$ ou sinon $d_1(x)=2$ et $x$est dans un triangle qui a au moins deux de ces sommets. Nous considérons plusieurs cas. La locution "dessiner une nouvelle arête" signifie "choisir une arête$e\in E\setminus E_1$ et ajoutez-le à $E_2$"; l'ensemble $E_2$ doit être composé de toutes les nouvelles arêtes choisies à l'étape 2.

Cas I. $d_1(x)=0$.

Dessinez deux nouvelles arêtes se joignant $x$ aux sommets de $W$.

Cas II. $d_1(x)=d_1(y)=1$ et $xy\in E_1$.

Dessinez deux nouvelles arêtes se joignant $x$ et $y$ à deux sommets distincts dans $W$.

Cas III. $d_1(x)=1$ et il y a des sommets $y\in V\setminus W$ et $z\in W$ tel que $xy,yz\in E_1$.

Si possible, dessinez une nouvelle jonction d'arête $x$ à un sommet dans $W$ distinct de $z$. Si ce n'est pas possible, dessinez deux nouvelles arêtes, joignant$x$ à $z$ et rejoindre $y$ à un autre sommet de $W$.

Cas IV. $d_1(x)=1$ et ni le cas II ni le cas III ne s'appliquent.

Dessiner une nouvelle jointure d'arête $x$ à un sommet dans $W$.

Cas V. $d_1(x)=d_1(y)=2$ et il y a un sommet $z\in W$ tel que $xy,xz,yz\in E_1$.

Dessinez une nouvelle arête joignant soit $x$ ou $y$ à un autre sommet de $W$.

Cas VI. $d_1(x)=d_1(y)=d_1(z)=2$ et $xy,xz,yz\in E_1$.

Dessinez deux nouvelles arêtes joignant deux sommets distincts dans $\{x,y,z\}$ aux sommets de $W$, pas nécessairement distinct.

Laisser $E_2$ être le sous-ensemble de $E\setminus E_1$ composé de toutes les nouvelles arêtes de l'étape 2. Il est facile de voir que le graphique $G_{1,2}=(V,E_1\cup E_2)$ sépare, et pour chaque $e\in E_2$ le graphique $G_{1,2}-e$ est non séparant.

Étape 3. Nous voulons trouver un ensemble minimal$F\subseteq E_1\cup E_2$ tel que $(V,F)$est un graphe de séparation; de manière équivalente, un ensemble maximal$S\subseteq E_1\cup E_2$ tel que $(V,(E_1\cup E_2)\setminus S)$ est un graphe de séparation.

Appeler un poste $S\subseteq E_1\cup E_2$ bien si$(V,(E_1\cup E_2)\setminus S)$est un graphe séparateur, mauvais si$(V,(E_1\cup E_2)\setminus S)$n'est pas un graphe de séparation. De toute évidence, un sous-ensemble d'un bon ensemble est bon. Nous voulons trouver un bon ensemble maximal.

Prétendre. Chaque mauvais ensemble$S\subseteq E_1\cup E_2$ contient un mauvais ensemble fini.

Preuve de réclamation. Supposer$S$est un mauvais ensemble. Depuis$\{e\}$ est mauvais à chaque fois $e\in E_2$, nous pouvons supposer que $S\subseteq E_1$. Par la définition d'un graphe séparateur, il y a des sommets$x,y\in V$ tel que $S$ contient un mauvais sous-ensemble $S_0$ composé d'arêtes incidentes avec $x$ ou $y$, C'est, $S_0\subseteq N_1(x)\cup N_1(y)$. Mais alors$S_0$ est fini, puisque le graphe $G_1$ est localement fini, étant sous-cubique.

Il découle du lemme de Claim et de Zorn qu'il existe un bon ensemble maximal $S\subseteq E_1\cup E_2$, d'où $(V,(E_1\cup E_2)\setminus S)$ est un sous-graphe couvrant de $G$ qui sépare au minimum.

Remarque. Un graphe à séparation minimale est sans triangle.

Supposer $G$ est un graphe de séparation, et supposons $G$ contient un triangle avec des sommets $x,y,z$. Au moins deux des trois sommets, disons$x$ et $y$, avoir au moins un diplôme $3$. Si$G-xy$ n'est pas un graphe de séparation, alors il doit y avoir un sommet de degré $2$ qui est adjacent à $x$ et $z$ ou pour $y$ et $z$; Disons$N(w)=\{x,z\}$. Mais maintenant c'est facile de voir ça$G-xz$ est un graphe de séparation, donc $G$ n'est pas une séparation minimale.