Täydellinen kaavio

Reunatäydellinen graafi on graafi, jonka viivakaavio on täydellinen . Vastaavasti nämä ovat kaavioita, joissa jokainen yksinkertainen parittoman pituinen sykli on kolmio [1] .

Graafi on reunatäydellinen, jos ja vain jos jokin sen kaksinkertaisesti kytketyistä komponenteista on kaksiosainen graafi , täydellinen graafi tai kolmioiden kirja [2] . Koska nämä kolme kaksinkertaisesti kytkettyä komponenttityyppiä ovat itsessään täydellisiä graafia, mikä tahansa reuna-täydellinen graafi on itsessään täydellinen [1] . Samanlaisista syistä mikä tahansa reuna-täydellinen graafi on pariteettigraafi [3] , Meinelin graafi [4] ja hyvin järjestetty graafi .

Reunatäydelliset graafit yleistävät kaksiosaiset graafit ja jakavat niiden kanssa ominaisuudet, että suurimmalla vastaavuudella ja pienimmällä pistepeitolla on sama koko ja kromaattinen indeksi on yhtä suuri kuin maksimiaste [5] .

Katso myös

Muistiinpanot

  1. ↑ 12 Trotter LE, Jr. Täydelliset viivakaaviot // Matemaattinen ohjelmointi . - 1977. - T. 12 , no. 2 . — S. 255–259 . - doi : 10.1007/BF01593791 .
  2. ↑ Frederic Maffray. Ytimet täydellisissä viivakaavioissa // Journal of Combinatorial Theory . - 1992. - T. 55 , no. 1 . - S. 1-8 . - doi : 10.1016/0095-8956(92)90028-V . .
  3. ↑ Martin Grötschel, László Lovász, Alexander Schrijver. Geometriset algoritmit ja kombinatorinen optimointi . – 2. - Springer-Verlag, Berliini, 1993. - V. 2. - S. 281. - (Algoritmit ja kombinatoriikka). — ISBN 3-540-56740-2 . - doi : 10.1007/978-3-642-78240-4 . .
  4. ↑ Annegret Wagler. Critical and anticritical edges in perfect graphs // Graph-Theoretic Concepts in Computer Science: 27th International Workshop, WG 2001, Boltenhagen, Saksa, 14.–16. kesäkuuta 2001, Proceedings. - Springer, 2001. - T. 2204. - S. 317-327. — (Luentomuistiinpanot tietojenkäsittelytieteestä). - doi : 10.1007/3-540-45477-2_29 . .
  5. ↑ Suoraviivaisilla kaavioilla // Matemaattinen ohjelmointi . - 1978. - T. 15 . - s. 236-238. - doi : 10.1007/BF01609025 . .