Teljes páros gráf

Sablon:Gráf infobox A teljes páros gráf olyan páros gráf, ahol mindkét partíció minden csúcsára fennáll, hogy vezet belőle él a másik partíció minden csúcsába. A teljes k-részes gráf speciális esete, ahol k=2.

Definíció

Teljes páros gráfnak nevezünk valamely $G=(V_1+V_2,E)$ páros gráfot, ha bármely $v_1\in V_1$ és $v_2\in V_2$ csúcspárra létezik $\{v_1,v_2\}\in E$ él.

$K_{m,n}$ szimbólummal jelöljük azt a teljes páros gráfot, ahol $\left|V_1\right|=m$ és $\left|V_2\right|=n$. A jelölés Kazimierz Kuratowski lengyel matematikus nevét őrzi.

Tulajdonságok

• a $K_{m,n}$ gráf $m+n$ csúcsot és $m\cdot n$ élt tartalmaz
• a Kuratowski-tétel szerint síkbarajzolható gráf nem tartalmazhat a $K_{3,3}$ gráffal topologikusan izomorf részgráfot.
• a definíció következményeként $K_{m,n}=K_{n,m}$
• a $K_{m,n}$ gráf összefüggő
• élgráfjai bástyagráfok
• csillagkromatikus száma ${\chi }_s(G)=min(m,n)+1$.

Speciális esetek

Egy K_m,n teljes páros gráf akkor és csak akkor körmentes, ha m=1 vagy n=1. Ilyen esetben lehet beszélni csillaggráfról (illetve csillagtopológiáról):

• 
  S₃ = K_1,3
• 
  S₄ = K_1,4
• 
  S₅ = K_1,5
• 
  S₆ = K_1,6

Speciális jelentősége van még a gráfok síkbarajzolhatóságában a K_3,3 gráf (három ház–három kút-gráf):

• 
  K_3,3

Ha m=n, akkor a gráf csúcstranzitív.

Lásd még

• Páros gráf
• Teljes gráf

Irodalom

• Sablon:Citation.
• Sablon:Citation Sablon:Wayback