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

nincs szerkesztési összefoglaló
a (Bot: 14 interwiki link migrálva a Wikidata d:q913598 adatába)
Nincs szerkesztési összefoglaló
 
== 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 páros 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.
 
== Tulajdonságok ==
* a <math>K_{m,n}</math> gráf <math>m + n</math> csúcsot és <math>m \cdot n</math> életélt 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 definíció következményeként <math>K_{m,n} = K_{n,m}</math>