Chordální bipartitní graf - Chordal bipartite graph - Wikipedia

V matematický oblast teorie grafů, a chordální bipartitní graf je bipartitní graf B = (X,Y,E) ve kterém každý cyklus o délce nejméně 6 palců B má akord, tj. hrana, která spojuje dva vrcholy, které jsou od sebe vzdáleny> 1 v cyklu.[1]Lepší název by byl slabě chordální a bipartitní, protože chordální bipartitní grafy obecně nejsou akordický jak ukazuje indukovaný cyklus délky 4.

Charakterizace

Chordální bipartitní grafy mají různé charakterizace, pokud jde o perfektní eliminace objednávek, hypergrafy a matice. Jsou úzce spjaty s silně chordální grafy. Podle definice mají chordální bipartitní grafy a zakázaná charakterizace podgrafu jako grafy, které žádné neobsahují indukovaný cyklus o délce 3 nebo délce nejméně 5 (tzv. otvory) jako indukovaný podgraf. Tedy graf G je chordální bipartitní právě tehdy G je bez trojúhelníků a bez děr. v Golumbic (1980), jsou zmíněny dvě další charakterizace: B je chordální bipartitní právě tehdy, když každý minimální oddělovač hran vyvolá v něm úplný bipartitní podgraf B právě když je každý indukovaný podgraf dokonalou eliminační bipartitou.

Martin Farber ukázal: Graf je silně chordální právě tehdy, když je graf bipartitního výskytu jeho klikového hypergrafu chordální bipartit. [2]

Podobná charakterizace platí i pro hypergraf uzavřeného sousedství: Graf je silně chordální právě tehdy, když je bipartitním grafem dopadu jeho hypergrafu uzavřeného sousedství chordální bipartit.[3]

Další výsledek nalezený Eliasem Dahlhausem je: Bipartitní graf B = (X,Y,E) je chordální bipartitní právě tehdy, když dělený graf vyplývající z výroby X klika je silně akordická.[4]

Bipartitní graf B = (X,Y,E) je chordální bipartitní právě tehdy, když každý indukovaný podgraf z B má maximum X-sousední objednávání a maximální Y-sousedství objednávat.[5]

Různé výsledky popisují vztah mezi chordálními bipartitními grafy a zcela vyváženými sousedními hypergrafy bipartitních grafů.[6]

Charakterizace chordálních bipartitních grafů z hlediska křižovatkových grafů souvisejících s hypergrafy je uvedena v.[7]

Bipartitní graf je chordální bipartitní právě tehdy, když je jeho matice sousedství zcela vyvážená právě tehdy, pokud je matice sousednosti bez gama.[8]

Uznání

Chordální bipartitní grafy lze rozpoznat včas O (min (n2, (n + m) log n)) pro graf s n vrcholy a m hrany.[9]

Složitost problémů

Různé problémy, jako je Hamiltonovský cyklus,[10] Steinerův strom [11] a efektivní nadvláda [12] zůstaňte NP-kompletní na chordálních bipartitních grafech.

Různé další problémy, které lze efektivně vyřešit u bipartitních grafů, lze efektivněji vyřešit u chordálních bipartitních grafů, jak je popsáno v [13]

Související třídy grafů

Každý chordální bipartitní graf je a modulární graf. Akordické bipartitní grafy zahrnují kompletní bipartitní grafy a bipartita vzdálenostně dědičné grafy.[14]

Poznámky

  1. ^ Golumbic (1980), str. 261, Brandstädt, Le & Spinrad (1999), Definice 3.4.1, str. 43.
  2. ^ Farber (1983); Brandstädt, Le & Spinrad (1999), Věta 3.4.1, s. 43.
  3. ^ Brandstädt (1991)
  4. ^ Brandstädt, Le & Spinrad (1999), Dodatek 8.3.2, str. 129.
  5. ^ Dragan & Voloshin (1996)
  6. ^ Brandstädt, Le & Spinrad (1999) „Věty 8.2.5, 8.2.6, s. 126–127.
  7. ^ Huang (2006)
  8. ^ Farber (1983)
  9. ^ Lubiw (1987); Paige & Tarjan (1987); Spinrad (1993); Spinrad (2003).
  10. ^ Müller (1996)
  11. ^ Müller & Brandstädt (1987)
  12. ^ Lu & Tang (2002)
  13. ^ Spinrad (2003).
  14. ^ Chordální bipartitní grafy, Informační systém o třídách grafů a jejich začlenění, vyvoláno 2016-09-30.

Reference

  • Brandstädt, Andreas (1991), „Třídy bipartitních grafů souvisejících s akordovými grafy“, Diskrétní aplikovaná matematika, 32: 51–60, doi:10.1016 / 0166-218x (91) 90023-p.
  • Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), „Dually Chordal Graphs“, SIAM Journal on Discrete Mathematics, 11: 437–455, doi:10.1137 / s0895480193253415.
  • Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Třídy grafů: PrůzkumMonografie SIAM o diskrétní matematice a aplikacích, ISBN  0-89871-432-X.
  • Dragan, Feodor; Voloshin, Vitaly (1996), „Incident graphs of biacyclic hypergraphs“, Diskrétní aplikovaná matematika, 68: 259–266, doi:10.1016 / 0166-218x (95) 00070-8.
  • Farber, M. (1983), „Charakterizace silně chordálních grafů“, Diskrétní matematika, 43 (2–3): 173–189, doi:10.1016 / 0012-365X (83) 90154-1.
  • Golumbic, Martin Charles (1980), Algoritmická teorie grafů a dokonalé grafyAkademický tisk, ISBN  0-12-289260-7.
  • Huang, Jing (2006), „Reprezentativní charakterizace chordálních bipartitních grafů“, Journal of Combinatorial Theory, Series B, 96 (5): 673–683, doi:10.1016 / j.jctb.2006.01.001.
  • Lu, Chin Lung; Tang, Chuan Yi (2002), „Vážená efektivní nadvláda na dokonalých grafech“, Diskrétní aplikovaná matematika, 117: 163–182, doi:10.1016 / s0166-218x (01) 00184-6.
  • Lubiw, A. (1987), „Doubly lexical orderings of matrices“, SIAM Journal on Computing, 16 (5): 854–879, doi:10.1137/0216057.
  • Müller, Haiko (1996), „Hamiltonovy obvody v chordálních bipartitních grafech“, Diskrétní matematika, 156: 291–298, doi:10.1016 / 0012-365x (95) 00057-4.
  • Müller, Haiko; Brandstädt, Andreas (1987), „NP-úplnost Steinerova stromu a dominující sady pro chordální bipartitní grafy“, Teoretická informatika, 53: 257–265, doi:10.1016/0304-3975(87)90067-3.
  • Paige, R .; Tarjan, R. E. (1987), "Tři algoritmy upřesnění oddílu", SIAM Journal on Computing, 16 (6): 973–989, doi:10.1137/0216062.
  • Spinrad, Jeremy (1993), „Dvojnásobné lexikální uspořádání hustých matic 0–1“, Dopisy o zpracování informací, 45 (2): 229–235, doi:10.1016 / 0020-0190 (93) 90209-R.
  • Spinrad, Jeremy (2003), Efektivní grafická reprezentaceMonografie Fields Institute, Americká matematická společnost, ISBN  0-8218-2815-0.