Teljes páros gráf

A Wikipédiából, a szabad enciklopédiából
Teljes páros gráf
Complete bipartite graph K3,2.svg
K3,2

Névadó Kazimierz Kuratowski
Csúcsok száma n + m
Élek száma mn
Átmérő 2
Kromatikus szám 2
Élkromatikus szám max{m, n}
Automorfizmusok 2m!n! ha m=n, különben m!n!

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.

Definíció[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

Speciális esetek[szerkesztés | forrásszöveg szerkesztése]

Egy Km,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):

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

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

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Irodalom[szerkesztés | forrásszöveg szerkesztése]

Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, p. 17, ISBN 3-540-26182-6, <http://diestel-graph-theory.com/index.html>.

Bondy, John Adrian & Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, p. 5, ISBN 0-444-19451-7, <http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html>