Caracterisació de grafos prohibits
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 | 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,0 1,1 1,2 Diestel, Reinhard(2000).«Graph Theory».Springer-Verlag.173.
- ↑ .
- ↑ 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..
- ↑ 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..
- ↑ Béla Bollobás (1998) "Modern Graph Theory", Springer, ISBN 0-387-98488-7 9
- ↑ 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..
- ↑ .
- ↑ .
- ↑ 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..
- ↑ 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..
- ↑ 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..
- ↑ 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,0 13,1 .
- ↑ Website
- Este artícul conté una traducció derivada de «Caracterisació de grafos prohibidos» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.