Skojarzenia w grafach

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
mariolkowicz
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 9 gru 2009, o 00:48
Płeć: Kobieta
Lokalizacja: RZESZÓW

Skojarzenia w grafach

Post autor: mariolkowicz »

\(\displaystyle{ Niech \emptyset \neq X \subset V(G)}\). Podzbiór X jest skojarzony z podzbiorem\(\displaystyle{ \ $Y \subseteq V(G)\backslash X$}\) jeżeli istnieje skojarzenie\(\displaystyle{ $M\subseteq E(G)$}\) takie, że każda krawędźŸ ze zbioru M jest incydentna z wierzchołkiem X oraz wierzchołkiem ze zbioru Y i każdy wierzchołek ze zbioru X jest incydentny z pewną krawędzia ze skojarzenia M.
no i jest tu taki przykład
\(\displaystyle{ $X=\{x_2,x_3,x_4\}$ , $Y=\{x_5,x_6\}$}\)
\(\displaystyle{ \begin{pspicture}(0,-0.18)(6.94,1.9)
\psdots[dotsize=0.16](0.5053125,0.66)
\psdots[dotsize=0.16](1.7053126,0.68)
\psdots[dotsize=0.16](2.9053125,0.66)
\psdots[dotsize=0.16](4.1053123,0.68)
\psdots[dotsize=0.16](5.3053126,0.66)
\psline[linewidth=0.04cm](0.5253125,0.66)(1.7453125,0.68)
\psline[linewidth=0.04cm](4.1653123,0.68)(5.2653127,0.66)
\psarc[linewidth=0.04](4.6253123,0.0){1.88}{19.405972}{157.10945}
\psdots[dotsize=0.16](6.3853126,0.68)
\psellipse[linewidth=0.04,linestyle=dashed,dash=0.16cm 0.16cm,dimen=outer](2.872656,0.48)(1.4926562,0.66)
\psellipse[linewidth=0.04,linestyle=dashed,dash=0.16cm 0.16cm,dimen=outer](5.86,0.55)(1.08,0.53)
\usefont{T1}{ptm}{m}{n}
\rput(0.40234375,0.37){$x_1$}
\usefont{T1}{ptm}{m}{n}
\rput(1.736875,0.45){$x_2$}
\usefont{T1}{ptm}{m}{n}
\rput(2.9693751,0.43){$x_3$}
\usefont{T1}{ptm}{m}{n}
\rput(4.058125,0.41){$x_4$}
\usefont{T1}{ptm}{m}{n}
\rput(5.3125,0.41){$x_5$}
\usefont{T1}{ptm}{m}{n}
\rput(6.4375,0.43){$x_6$}
\end{pspicture}}\)

Jak mam ten rysunek opisać
ODPOWIEDZ