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

Ugrás a navigációhoz Ugrás a kereséshez
a
Bot: következő módosítása: zh:完全二分图; kozmetikai változtatások
[ellenőrzött változat][ellenőrzött változat]
a (Bot: következő módosítása: fa:گراف کامل دوبخشی)
a (Bot: következő módosítása: zh:完全二分图; kozmetikai változtatások)
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.
== Definíció ==
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.
 
== Példák ==
<gallery>
Kép:Complete bipartite graph K3,1.svg|''K''<sub>1,3</sub>
Kép:Complete bipartite graph K3,3.svg|''K''<sub>3,3</sub>
</gallery>
== Tulajdonságok ==
* 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ő
 
== Lásd még ==
* [[Páros gráf]]
* [[Teljes gráf]]
[[th:กราฟสองส่วนบริบูรณ์]]
[[vi:Đồ thị hai phía đầy đủ]]
[[zh:完全二图]]
158 310

szerkesztés

Navigációs menü