„Teljes páros gráf” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Bot: következő módosítása: fa:گراف کامل دوبخشی |
a Bot: következő módosítása: zh:完全二分图; kozmetikai változtatások |
||
| 1. sor: | 1. sor: | ||
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. |
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ó== |
== 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. |
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. |
<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== |
== Példák == |
||
<gallery> |
<gallery> |
||
Kép:Complete bipartite graph K3,1.svg|''K''<sub>1,3</sub> |
Kép:Complete bipartite graph K3,1.svg|''K''<sub>1,3</sub> |
||
| 11. sor: | 11. sor: | ||
Kép:Complete bipartite graph K3,3.svg|''K''<sub>3,3</sub> |
Kép:Complete bipartite graph K3,3.svg|''K''<sub>3,3</sub> |
||
</gallery> |
</gallery> |
||
==Tulajdonságok== |
== 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 <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 [[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ő |
* a <math>K_{m,n}</math> gráf összefüggő |
||
==Lásd még== |
== Lásd még == |
||
* [[Páros gráf]] |
* [[Páros gráf]] |
||
* [[Teljes gráf]] |
* [[Teljes gráf]] |
||
| 30. sor: | 30. sor: | ||
[[th:กราฟสองส่วนบริบูรณ์]] |
[[th:กราฟสองส่วนบริบูรณ์]] |
||
[[vi:Đồ thị hai phía đầy đủ]] |
[[vi:Đồ thị hai phía đầy đủ]] |
||
[[zh:完全二 |
[[zh:完全二分图]] |
||
A lap 2009. június 12., 08:52-kori változata
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 páros gráfot, ha bármely és csúcspárra létezik él.
szimbólummal jelöljük azt a páros teljes gráfot, ahol és . A jelölés Kazimierz Kuratowski lengyel matematikus nevét őrzi.
Példák
-
K1,3 -
K2,3 -
K3,3
Tulajdonságok
- a gráf csúcsot és élet tartalmaz
- a Kuratowski-tétel szerint síkbarajzolható gráf nem tartalmazhat a gráffal topologikusan izomorf részgráfot.
- a gráf összefüggő
