13. Páros gráfok

Question 1

Páros (kétpólusú) gráf

Answer 1

A $G=(V,E)$ gráfot kétpólusú vagy páros gráfnak nevezzük, ha $V$ csúcshalmaza felbontható 2 nemüres részre úgy, hogy élek csak különböző pólusok között húzódhatnak, azaz $V=A∪B, A∩B = ∅$, $A,B \neq ∅$ és $E⊆ {{a, b} : a ∈ A, b ∈ B}$. Bármely körének hossza páros hosszúságú. 2 színezhető, van rá gyors algoritmus. (választok egy kezdőpontot, beszínezem 1 színnel(piros), átmegyek a szomszédjába, beszínezem más színnel(kékkel), majd a következő szomszéd ahol még nem jártunk, piros színnel, és így tovább. Minden páros hosszúságú kiszínezhető, a páratlanok nem! mellékelve egy ábra)

Question 2

Kétpólusú gráf, Teljes kétpólusú gráf:

Answer 2

Kétpólusú gráf:

• Egy $G = (V,E)$ gráf pontosan akkor kétpólusú (páros), ha $G$ minden köre páros hosszúságú, azaz $G$-ben nincs páratlan hosszú kör.

Teljes kétpólusú gráf:

• Egy olyan kétpólusú egyszerű gráf, amelyben a pólusok méretei $|A| = m$ és $|B| = n$, és E az összes lehetséges élt tartalmazza, vagyis $E={{a, b} : a ∈ A, b ∈ B}$. Jele: $K_{m−n}$

Question 3

Lefogó pontrendszer, Kőnig Dénes tétele:

Answer 3

Def: Tetszőleges $G=(V,E)$ gráf esetén
1.) $Y \subseteq V$ lefogó pont-/csúcsrendszer, ha a G gráf minden élének valamelyik végpontja Y-ba esik.
2.) $m(G):=$ minimális lefogó pontrendszer elemszáma, és $M(G):=$ maximális független élrendszer elemszáma.
3.) $m(G)≥M(G)$

Kőnig Dénes tétele:

• Páros gráf esetén $m(G)=M(G)$

Question 4

Független élek:

Answer 4

• Élek egy tetszőleges $F⊆E$ halmaza független vagy diszjunkt élrendszer, más néven párosítás, ha $e_i ∩ e_j = ∅$ minden $e_i , e_j ∈ F(i \neq j)$ tetszőleges élek közül bármely kettőnek nincs közös végpontja.
• $F \subseteq E$ lefedő élrendszer, ha $∪F=V$, azaz F-beli élek a gráf minden csúcsát tartalmazzá
• A független lefogó élrendszereket teljes párosításnak, vagy 1 faktornak nevezzük

Question 5

Szomszédsági halmaz:

Answer 5

Tetszőleges $X \sube V$ csúcshalmaz esetén legyen $N(X)$ az X szomszédainak halmaza (N- neighbor), azaz legyen

$N(X) := { y \in V\ |\ \exists\ x \in X\ { x,y } \in E }$

Question 6

Hall tétele:

Answer 6

• Tetszőleges $G=(V,E)$, $V=(V_1∪V_2)$ kétpólusú gráfban, ha az egyik pólus m-elemű, |V1|=m, akkor pontosan akkor létezik m élből álló független élrendszer, ha
  $|N(X)| ≥ |X| ∀X ⊆ V_1$,
  azaz minden X szögponthalmaznak legalább annyi szomséda van, mint ahány eleme.