„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
Nincs szerkesztési összefoglaló |
|||
1. sor: | 1. sor: | ||
{{gráf infobox |
{{gráf infobox |
||
| név |
| név = Teljes páros gráf |
||
| kép |
| kép = Complete bipartite graph K3,2.svg |
||
| képaláírás = '''K<sub>3,2</sub>''' |
| képaláírás = '''K<sub>3,2</sub>''' |
||
| névadó = Kazimierz Kuratowski |
| névadó = Kazimierz Kuratowski |
||
| csúcsok = ''n'' + ''m'' |
| csúcsok = ''n'' + ''m'' |
||
| élek |
| élek = ''mn'' |
||
| sugár |
| sugár = |
||
| átmérő = 2 |
| átmérő = 2 |
||
| kromatikus szám = 2 |
| kromatikus szám = 2 |
||
| élkromatikus szám = max{''m'', ''n''} |
| élkromatikus szám = max{''m'', ''n''} |
||
| egyéb = |
| egyéb = |
||
| automorfizmusok |
| automorfizmusok = 2''m''!''n''! ha ''m''=''n'', különben ''m''!''n''! |
||
| Girth paraméter= 4 |
| Girth paraméter= 4 |
||
| jelölés = <math>K_{m,n}</math> |
| jelölés = <math>K_{m,n}</math> |
||
29. sor: | 29. sor: | ||
== Speciális esetek == |
== Speciális esetek == |
||
Egy K<sub>m,n</sub> teljes páros gráf akkor és csak akkor körmentes, ha ''m=1'' vagy |
Egy K<sub>m,n</sub> 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): |
||
<gallery> |
<gallery> |
||
Kép:Steiner 3 points.svg|'''S<sub>3</sub> = K<sub>1,3</sub>''' |
Kép:Steiner 3 points.svg|'''S<sub>3</sub> = K<sub>1,3</sub>''' |
||
59. sor: | 59. sor: | ||
}}. |
}}. |
||
* {{citation |
* {{citation |
||
| last1=Bondy | first1=John Adrian |
| last1=Bondy | first1=John Adrian |
||
| last2=Murty | first2=U. S. R. |
| last2=Murty | first2=U. S. R. |
||
| title=Graph Theory with Applications |
| title=Graph Theory with Applications |
||
| year=1976 |
| year=1976 |
A lap 2014. október 29., 19:42-kori változata
Teljes páros gráf | |
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! |
Jelölés |
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ó
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 teljes páros gráfot, ahol és . A jelölés Kazimierz Kuratowski lengyel matematikus nevét őrzi.
Tulajdonságok
- a gráf csúcsot és élt tartalmaz
- a Kuratowski-tétel szerint síkbarajzolható gráf nem tartalmazhat a gráffal topologikusan izomorf részgráfot.
- a definíció következményeként
- a gráf összefüggő
Speciális esetek
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):
-
S3 = K1,3
-
S4 = K1,4
-
S5 = K1,5
-
S6 = K1,6
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):
-
K3,3
Ha m=n, akkor a gráf csúcstranzitív.
Lásd még
Irodalom
- 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>