Kompletní bipartitní graf - Complete bipartite graph

Kompletní bipartitní graf
	Kompletní bipartitní graf s m = 5 a n = 3
Vrcholy	n + m
Hrany	mn
Poloměr
Průměr
Obvod
Automorfismy
Chromatické číslo	2
Chromatický index	max {m, n}
Spektrum
Zápis
	Tabulka grafů a parametrů

V matematický pole teorie grafů, a kompletní bipartitní graf nebo biclique je zvláštní druh bipartitní graf kde každý vrchol první sady je spojen s každým vrcholem druhé sady.^[1]^[2]

Samotná teorie grafů je obvykle datována jako začátek Leonhard Euler 1736 prací na Sedm mostů v Königsbergu. Nicméně, kresby kompletních bipartitních grafů bylo vytištěno již v roce 1669 v souvislosti s vydáním děl Ramon Llull editoval Athanasius Kircher.^[3]^[4] Samotný Llull vytvořil podobné kresby kompletní grafy o tři století dříve.^[3]

Definice

A kompletní bipartitní graf je graf, jehož vrcholy lze rozdělit do dvou podmnožin PROTI₁ a PROTI₂ takže žádná hrana nemá oba koncové body ve stejné podmnožině a každá možná hrana, která by mohla spojovat vrcholy v různých podmnožinách, je součástí grafu. To znamená, že je bipartitní graf (PROTI₁, PROTI₂, E) tak, že pro každé dva vrcholy proti₁ ∈ PROTI₁ a proti₂ ∈ PROTI₂, proti₁proti₂ je hrana v E. Kompletní bipartitní graf s oddíly o velikosti |PROTI₁| = m a |PROTI₂| = n, je označen K._{m, n};^[1]^[2] každé dva grafy se stejným zápisem jsou izomorfní.

Příklady

The hvězdné grafy K._1,3, K._1,4, K._1,5, a K._1,6.

Kompletní bipartitní graf

K. 4,7

což ukazuje Problém továrny na cihly v Turánu se 4 skladovacími místy (žluté skvrny) a 7 pecemi (modré skvrny) vyžaduje 18 přechodů (červené tečky)

Pro všechny k, K._1,k se nazývá a hvězda.^[2] Všechny úplné bipartitní grafy, které jsou stromy jsou hvězdy.
- Graf K._1,3 se nazývá a dráp, a slouží k definování grafy bez drápů.^[5]
Graf K._3,3 se nazývá obslužný graf. Toto použití pochází ze standardní matematické hádanky, ve které musí být každý ze tří nástrojů propojen se třemi budovami; je nemožné vyřešit bez přechodů kvůli neplanárnost z K._3,3.^[6]

Maximální bicliques nalezené jako podgrafy digrafu relace se nazývají koncepty. Když se mřížka vytvoří spojením těchto podgrafů, má vztah Indukovaná koncepce mříž. Tento typ analýzy vztahů se nazývá formální koncepční analýza.

Vlastnosti

Příklad K_str,str kompletní bipartitní grafy^[7]
K._3,3	K._4,4	K._5,5

3 zbarvení hran	4 barvení hran	5 barev hran
Pravidelné složité polygony formuláře 2 {4}str mít kompletní bipartitní grafy s 2str vrcholy (červené a modré) a str² 2-hrany. Mohou být také nakresleny jako str zbarvení hran.

Vzhledem k bipartitnímu grafu se testuje, zda obsahuje kompletní bipartitní podgraf K._i,i pro parametri je NP-kompletní problém.^[8]
A rovinný graf nemůže obsahovat K._3,3 jako Méně důležitý; an vnější rovinný graf nemůže obsahovat K._3,2 jako nezletilý (To nejsou dostatečné podmínky pro rovinnost a vnější rovinnost, ale nutné). Naopak každý neplanární graf obsahuje buď K._3,3 nebo kompletní graf K.₅ jako nezletilý; tohle je Wagnerova věta.^[9]
Každý kompletní bipartitní graf. K._n,n je Mooreův graf a (n,4)-klec.^[10]
Kompletní bipartitní grafy K._n,n a K._n,n+1 mít maximální možný počet hran ze všech grafy bez trojúhelníků se stejným počtem vrcholů; tohle je Mantelova věta. Výsledek Mantel byl zobecněn na k- částečné grafy a grafy, které se vyhýbají větším kliky jako podgrafy v Turánova věta, a tyto dva kompletní bipartitní grafy jsou příklady Turánovy grafy, extrémní grafy pro tento obecnější problém.^[11]
Kompletní bipartitní graf K._m,n má číslo pokrývající vrchol z min{m, n} a číslo pokrývající hranu z max{m, n}.
Kompletní bipartitní graf K._m,n má maximální nezávislá sada velikosti max{m, n}.
The matice sousedství kompletního bipartitního grafu K._m,n má vlastní čísla √nm, −√nm a 0; s multiplicitou 1, 1 a n+m-2 příslušně.^[12]
The Laplaciánská matice kompletního bipartitního grafu K._m,n má vlastní čísla n+m, n, ma 0; s multiplicitou 1, m−1, n-1, respektive 1.
Kompletní bipartitní graf K._m,n má mⁿ⁻¹ n^m−1 klenout se nad stromy.^[13]
Kompletní bipartitní graf K._m,n má maximální shoda velikosti min{m,n}.
Kompletní bipartitní graf K._n,n má pořádný n-obarvení okraje odpovídající a Latinský čtverec.^[14]
Každý úplný bipartitní graf je a modulární graf: každá trojice vrcholů má medián, který patří k nejkratším cestám mezi každou dvojicí vrcholů.^[15]

Viz také

Bezblikový graf, třída řídkých grafů definovaná vyhýbáním se úplným bipartitním podgrafům
Korunní graf, graf vytvořený odstraněním a perfektní shoda z úplného bipartitního grafu
Kompletní multipartitní graf, zobecnění úplných bipartitních grafů na více než dvě sady vrcholů
Biclique útok

Reference

^ ^A ^b Bondy, John Adrian; Murty, USA (1976), Teorie grafů s aplikacemi, Severní Holandsko, s.5, ISBN 0-444-19451-7.
^ ^A ^b ^C Diestel, Reinhard (2005), Teorie grafů (3. vyd.), Springer, ISBN 3-540-26182-6. Elektronické vydání, strana 17.
^ ^A ^b Knuth, Donald E. (2013), „Dva tisíce let kombinatoriky“, Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, s. 7–37, ISBN 0191630624.
^ Přečtěte si, Ronald C .; Wilson, Robin J. (1998), Atlas grafů, Clarendon Press, str. ii, ISBN 9780198532897.
^ Lovász, László; Plummer, Michael D. (2009), Teorie shody „Providence, RI: AMS Chelsea, s. 1“ 109, ISBN 978-0-8218-4759-6, PAN 2536865. Opravený dotisk originálu z roku 1986.
^ Gries, David; Schneider, Fred B. (1993), Logický přístup k diskrétní matematice, Springer, str. 437, ISBN 9780387941158.
^ Coxeter, Pravidelné složité polytopy, druhé vydání, str.114
^ Garey, Michael R.; Johnson, David S. (1979), „[GT24] Balanced complete bipartite subgraph“, Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W. H. Freeman, str.196, ISBN 0-7167-1045-5.
^ Diestel 2005, str. 105
^ Biggs, Norman (1993), Algebraická teorie grafů, Cambridge University Press, str. 181, ISBN 9780521458979.
^ Bollobás, Béla (1998), Teorie moderních grafů, Postgraduální texty z matematiky, 184, Springer, str. 104, ISBN 9780387984889.
^ Bollobás (1998), str. 266.
^ Jungnickel, Dieter (2012), Grafy, sítě a algoritmy, Algoritmy a výpočty v matematice, 5, Springer, str. 557, ISBN 9783642322785.
^ Jensen, Tommy R .; Toft, Bjarne (2011), Problémy s barvením grafů, Wiley Series v diskrétní matematice a optimalizaci, 39, Wiley, str. 16, ISBN 9781118030745.
^ Bandelt, H.-J .; Dählmann, A .; Schütte, H. (1987), „Absolutní zatažení bipartitních grafů“, Diskrétní aplikovaná matematika, 16 (3): 191–215, doi:10.1016 / 0166-218X (87) 90058-8, PAN 0878021.

[bm-1] A ^b Bondy, John Adrian; Murty, USA (1976), Teorie grafů s aplikacemi, Severní Holandsko, s.5, ISBN 0-444-19451-7.

[d-2] A ^b ^C Diestel, Reinhard (2005), Teorie grafů (3. vyd.), Springer, ISBN 3-540-26182-6. Elektronické vydání, strana 17.

[knuth-3] A ^b Knuth, Donald E. (2013), „Dva tisíce let kombinatoriky“, Wilson, Robin; Watkins, John J. (eds.), Combinatorics: Ancient and Modern, Oxford University Press, s. 7–37, ISBN 0191630624.

[4] Přečtěte si, Ronald C .; Wilson, Robin J. (1998), Atlas grafů, Clarendon Press, str. ii, ISBN 9780198532897.

[5] Lovász, László; Plummer, Michael D. (2009), Teorie shody „Providence, RI: AMS Chelsea, s. 1“ 109, ISBN 978-0-8218-4759-6, PAN 2536865. Opravený dotisk originálu z roku 1986.

[6] Gries, David; Schneider, Fred B. (1993), Logický přístup k diskrétní matematice, Springer, str. 437, ISBN 9780387941158.

[7] Coxeter, Pravidelné složité polytopy, druhé vydání, str.114

[8] Garey, Michael R.; Johnson, David S. (1979), „[GT24] Balanced complete bipartite subgraph“, Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W. H. Freeman, str.196, ISBN 0-7167-1045-5.

[9] Diestel 2005, str. 105

[10] Biggs, Norman (1993), Algebraická teorie grafů, Cambridge University Press, str. 181, ISBN 9780521458979.

[11] Bollobás, Béla (1998), Teorie moderních grafů, Postgraduální texty z matematiky, 184, Springer, str. 104, ISBN 9780387984889.

[12] Bollobás (1998), str. 266.

[13] Jungnickel, Dieter (2012), Grafy, sítě a algoritmy, Algoritmy a výpočty v matematice, 5, Springer, str. 557, ISBN 9783642322785.

[14] Jensen, Tommy R .; Toft, Bjarne (2011), Problémy s barvením grafů, Wiley Series v diskrétní matematice a optimalizaci, 39, Wiley, str. 16, ISBN 9781118030745.

[15] Bandelt, H.-J .; Dählmann, A .; Schütte, H. (1987), „Absolutní zatažení bipartitních grafů“, Diskrétní aplikovaná matematika, 16 (3): 191–215, doi:10.1016 / 0166-218X (87) 90058-8, PAN 0878021.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

Kompletní bipartitní graf
Kompletní bipartitní graf s m = 5 a n = 3
Vrcholy	n + m
Hrany	mn
Poloměr	${ displaystyle left {{ begin {pole} {ll} 1 & m = 1 vee n = 1 2 & { text {jinak}} end {pole}} vpravo.}$
Průměr	${ displaystyle left {{ begin {pole} {ll} 1 & m = n = 1 2 & { text {jinak}} end {pole}} doprava.}$
Obvod	${ displaystyle left {{ begin {pole} {ll} infty & m = 1 lor n = 1 4 & { text {jinak}} end {pole}} vpravo.}$
Automorfismy	${ displaystyle left {{ begin {pole} {ll} 2 m! n! & n = m m! n! & { text {jinak}} end {pole}} vpravo.}$
Chromatické číslo	2
Chromatický index	max {m, n}
Spektrum	${ displaystyle left {0 ^ {n + m-2}, ( pm { sqrt {nm}}) ^ {1} right }}$
Zápis	${ displaystyle K_ {m, n}}$
Tabulka grafů a parametrů