Anar al contingut

Caracterisació de grafos prohibits

De L'Enciclopèdia, la wikipedia en valencià

En teoria de grafos, una branca de les matemàtiques, moltes famílies importants de grafos es poden descriure per mig d'un conjunt finit de grafos individuals que no pertanyen a la família i ademés exclouen tots els grafos de la família que contenen qualsevol d'estos grafos prohibits com subgrafos o menors (induïts).

Un eixemple prototípico d'este fenomen és el teorema de Kuratowski, que establix que un grafo és pla (és dir, es pot dibuixar sense creus en el pla) si i solament si no conté cap dels dos grafos prohibits, el grafo complet K5 i el grafo bipartit complet K3,3. Per a el teorema de Kuratowski, la noció de contindre és la de l'homeomorfisme de grafos, en la que una subdivisió d'un grafo apareix com subgrafo de l'atre. Aixina, tot grafo o be té un dibuix pla (en el cas del qual pertany a la família dels grafos plans) o té una subdivisió d'a lo manco un d'estos dos grafos com subgrafo (en el cas dels quals no pertany als grafos plans).

Definició

De manera més general, una caracterisació de grafos prohibits és un mètoto d'identificar una família d'estructures de grafos o hipergrafos, per mig de l'especificació de subestructura l'existència de les quals està prohibida dins de qualsevol grafo de la família. Les diferents famílies varien en la naturalea de lo que està prohibit. En general, una estructura G és membre d'una família ℱ si i solament si una subestructura prohibida no està continguda en G. Les subestructura prohibides podrien ser:

  • Subgrafos, grafos més chicotets obtinguts a partir de subconjunts de vèrtiços i arestes d'un grafo més gran.
  • Subgrafos induïts, grafos més chicotets obtinguts seleccionant un subconjunt dels vèrtiços i usant totes les arestes en abdós extrems en eixe subconjunt.
  • Subgrafos homeomorfos (també cridats menors), grafos més chicotets obtinguts a partir de subgrafos en colapsar camins de vèrtiços de grau dos en arestes simples.
  • Menors, grafos més chicotets obtinguts de subgrafos per contracció d'arestes arbitràries.

El conjunt d'estructures que tenen prohibit pertànyer a una família de grafos donada també pot denominar-se conjunt de obstrucció per a eixa família.

Les caracterisació de grafos prohibits es poden usar en algoritmia per a provar si un grafo pertany a una família determinada. En molts casos, és possible provar en temps polinòmic si un grafo dau conté algun dels membres del conjunt de obstrucció i, per lo tant, si pertany a la família definida per este conjunt.

Per a que una família tinga una caracterisació gràfica prohibida, en un tipo particular de subestructura, la família deu estar tancada baix subestructura, és dir, cada subestructura (d'un tipo donat) d'un grafo de la família deu ser un atre grafo de la família. De manera equivalent, si un grafo no és part de la família, tots els grafos més grans que ho continguen com a subestructura també deuen excloure's de la família. Quan açò és cert, sempre existix un conjunt d'obstrucció (el conjunt de grafos que no estan en la família pero les subestructura de la qual més chicotetes pertanyen totes a la família). No obstant, per a algunes nocions de lo que és una subestructura, este conjunt de obstrucció podria ser infinit. El teorema de Robertson-Seymour prova que, per al cas particular dels menors, una família tancada per menors sempre té un conjunt finit de obstrucció.

Llista de caracterisació prohibides per a grafos i hipergrafos

Família Obstrucció Relació Referència
Boscs Bucles, parells d'arestes paraleles, i cicles de totes les llongituts Subgrafo Definició
Un bucle (per a multigrafos) o triànguls K3 (per a grafos simples) Menor del grafo Definició
Boscs llineals [Un bucle / triàngul K3 (vore dalt)] i estrela K1,3 Menor del grafo Definició
Grafo lliure de garres Estrela K1,3 Subgrafo induït Definició
Grafos comparables Subgrafo induït
Grafos sense triànguls Triàngul K3 Subgrafo induït Definició
Grafos plans K5 i K3,3 Subgrafo homeomorfo Teorema de Kuratowski
K5 i K3,3 Menor del grafo Teorema de Wagner
Grafos plans exteriors K4 i K2,3 Menor del grafo Diestel (2000),[1] 107
Grafos 1-plans externs Sis menors prohibits Menor del grafo Auer et al. (2013)[2]
Grafos de genus fixe Un conjunt finit de obstrucció Menor del grafo Diestel (2000),[1] 275
Grafos d'àpiç Un conjunt finit de obstrucció Menor del grafo [3]
Grafos incrustats sense enllaços La família de Petersen Menor del grafo [4]
Grafos bipartits Cicles impars Subgrafo [5]
Grafos cordales Cicles de llongitut 4 o més Subgrafo induït [6]
Grafos perfectes Cicles de llongitut impar 5 o més o les seues complements Subgrafo induït [7]
Grafo rectilíneu de grafos 9 subgrafos prohibits Subgrafo induït [8]
Unions de grafos de grafos cactus El grafo diamant de quatre vèrtiços format en llevar una aresta del grafo complet K4 Menor del grafo [9]
Grafos d'escala K2,3 i el seu grafo dual Subgrafo homeomorfo [10]
Grafos dividits C4,C5,C¯4(=K2+K2) Subgrafo induït
2-conexo série-paralel (ample d'arbre ≤ 2, ample de branca ≤ 2) K4 Menor del grafo Diestel (2000),[1] 327
Ample d'arbre ≤ 3 K5, octaedre, prisma pentagonal, grafo de Wagner Menor del grafo [11]
Ample de branca ≤ 3 K5, octaedre, gaveta, grafo de Wagner Menor del grafo [12]
Grafos reducibles per complement (cografos) 4-vèrtiços recorregut P4 Subgrafo induït
Grafos perfectes trivialment 4-vèrtiços recorregut P4 i 4-vèrtiços cicle C4 Subgrafo induït [13]
Grafos llindar 4-vèrtiços recorregut P4, 4-vèrtiços cicle C4 i complement de C4 Subgrafo induït [13]
Grafo en rectes de 3-uniforme hipergrafos en rectes Una llista finita de subgrafos induïts prohibits en un grau mínim d'a lo manco 19 Subgrafo induït
Grafo en rectes de k-uniforme hipergrafos en rectes, k > 3 Una llista finita de subgrafos induïts prohibits en grau d'aresta mínim a lo manco 2k2 − 3k + 1 Subgrafo induït
Grafos ΔI-reducibles a un sol vèrtiç Una llista finita d'a lo manco 68 mil millons de sumes distintes de (1,2,3)-cliques Menor del grafo [14]
Teoremes generals
Una família definida per una propietat induïda-hereditària Un, possiblement no-finit, conjunt de obstrucció Subgrafo induït
Una família definida per una propietat de menor-hereditària Un conjunt finit de obstrucció Menor del grafo Teorema de Robertson-Seymour

Vore també

Referències

  1. ↑ 1,0 1,1 1,2 Diestel, Reinhard(2000).«Graph Theory».Springer-Verlag.173.
  2. ↑ .
  3. ↑ Gupta, A.; Impagliazzo, R.(1991).«Proc. 32nd IEEE Symposium on Foundations of Computer Science (FOCS '91)».IEEE Computer Society.: 802–811.doi:10.1109/SFCS.1991.185452..
  4. ↑ Robertson, Neil; Seymour, P. D.; Thomas, Robin(1993).«Linkless embeddings of graphs in 3-space».Bulletin of the American Mathematical Society.28(1): 84–89.doi:10.1090/S0273-0979-1993-00335-5..
  5. ↑ Béla Bollobás (1998) "Modern Graph Theory", Springer, ISBN 0-387-98488-7 9
  6. ↑ Kashiwabara, Toshinobu(1981).«Graph Theory and Algorithms, 17th Symposium of Research Institute of Electric Communication, Tohoku University, Sendai, Japan, October 24-25, 1980, Proceedings».Springer-Verlag.108: 171–181.doi:10.1007/3-540-10704-5_15..
  7. ↑ .
  8. ↑ .
  9. ↑ El-Mallah, Ehab; Colbourn, Charles J.(1988).«The complexity of some edge deletion problems».IEEE Transactions on Circuits and Systems.35(3): 354–362.doi:10.1109/31.1748..
  10. ↑ Takamizawa, K.; Nishizeki, Takao; Saito, Nobuji(1981).«Combinatorial problems on séries–parallel graphs».Discrete Applied Mathematics.3(1): 75–76.doi:10.1016/0166-218X(81)90031-7..
  11. ↑ Bodlaender, Hans L.(1998).«A partial k-arboretum of graphs with bounded treewidth».Theoretical Computer Science.209(1–2): 1–45.doi:10.1016/S0304-3975(97)00228-4..
  12. ↑ Bodlaender, Hans L.; Thilikos, Dimitrios M.(1999).«Graphs with branchwidth at most three».Journal of Algorithms.32(2): 167–194.doi:10.1006/jagm.1999.1011..
  13. ↑ 13,0 13,1 .
  14. ↑ Website