„Teljes páros gráf” változatai közötti eltérés

A '''teljes páros gráf''' olyan [[páros gráf]], ahol mindkét partíció minden csúcsára fennáll, hogy össze van kötve a másik partíció minden csúcsával.

Teljes páros gráfnak nevezünk valamely <math>G:=(V_1 + V_2, E)</math> [[páros gráf]]ot, ha bármely <math>v_1 \in V_1</math> és <math>v_2 \in V_2</math> csúcspárra létezik <math>\{ v_1, v_2 \} \in E</math> él.

 

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

 

<gallery>

Kép:Complete bipartite graph K3,1.svg|''K''_1,3

Kép:Complete bipartite graph K3,3.svg|''K''_3,3

</gallery>

* a <math>K_{m,n}</math> gráf <math>m + n</math> csúcsot és <math>m \cdot n</math> élet tartalmaz

* a [[Kuratowski-tétel]] szerint [[síkbarajzolható]] gráf nem tartalmazhat a <math>K_{3,3}</math> gráffal [[topologikusan izomorf]] részgráfot.

* a <math>K_{m,n}</math> gráf összefüggő

 

* [[Páros gráf]]

* [[Teljes gráf]]

[[th:กราฟสองส่วนบริบูรณ์]]

[[vi:Đồ thị hai phía đầy đủ]]