Korsningsdiagram - Intersection graph
I grafteorin är ett korsningsdiagram ett diagram som representerar mönstret för korsningar av en familj av uppsättningar . Vilket diagram som helst kan representeras som ett korsningsdiagram, men några viktiga specialklasser av grafer kan definieras av de typer av uppsättningar som används för att bilda en korsningsrepresentation av dem.
Formell definition
Formellt är ett korsningsdiagram G ett oriktat diagram bildat av en familj av uppsättningar
- S i , i = 0, 1, 2, ...
genom att skapa en spets v i för varje uppsättning S i , och anslutning av två hörn v i och v j av en kant närhelst de motsvarande två uppsättningarna har en icke-tom skärningspunkt, det vill säga,
- E ( G ) = {{ v i , v j } | i ≠ j , S i ∩ S j ≠ ∅}.
Alla grafer är korsningsdiagram
Någon oriktad graf G kan representeras som en skärnings graf: för varje vertex v jag av G , bilda en uppsättning S jag bestående av kanterna händelsen till v i ; då har två sådana uppsättningar en icke-snabb korsning om och endast om motsvarande hörn delar en kant. Erdős, Goodman & Pósa (1966) tillhandahåller en konstruktion som är mer effektiv (det vill säga kräver ett mindre totalt antal element i alla uppsättningarna S i kombinerat) där det totala antalet uppsättningselement är högst n 2 / 4 där n är antalet hörn i diagrammet. De tillskriver observationen att alla grafer är korsningsdiagram till Szpilrajn-Marczewski (1945) , men säger att även se Čulík (1964) . Den skärnings antal av ett diagram är den lägsta totala antalet element i varje skärnings representation av grafen.
Klasser av korsningsdiagram
Många viktiga graffamiljer kan beskrivas som korsningsdiagram för mer begränsade typer av uppsättningsfamiljer, till exempel uppsättningar härledda från någon form av geometrisk konfiguration:
- Ett intervalldiagram definieras som skärningsdiagrammet för intervall på den verkliga linjen, eller av anslutna underbilder av ett bandiagram .
- En likgiltighetsdiagram kan definieras som skärningsdiagrammet för enhetsintervall på den verkliga linjen
- En cirkelbågsdiagram definieras som skärningsdiagrammet för bågar på en cirkel .
- En polygoncirkeldiagram definieras som skärningspunkten mellan polygoner med hörn på en cirkel.
- En karaktärisering av ett ackorddiagram är som korsningsdiagrammet för anslutna underbilder av ett träd .
- En trapesformad graf definieras som skärningsdiagrammet för trapezider bildade av två parallella linjer. De är en generalisering av begreppet permutationsdiagram , i sin tur är de ett speciellt fall för familjen av komplementen till jämförbarhetsdiagram som kallas samförlikningsdiagram.
- En enhetsskivdiagram definieras som skärningsdiagrammet för enhetsskivor i planet.
- En cirkeldiagram är skärningsdiagrammet för en uppsättning ackord i en cirkel.
- Den cirkel packning teoremet anger att plana grafer är exakt skärnings grafer av familjer av slutna diskar i det plan som begränsas av icke-korsande cirklar.
- Scheinermans antagande (nu en teorem) säger att varje plan graf också kan representeras som ett skärningsdiagram över linjesegment i planet. Korsningsdiagram över linjesegment kan emellertid också vara icke-plana, och att känna igen korsningsdiagram över linjesegment är komplett för realens existentiella teori ( Schaefer 2010 ).
- Den linjegraf av en graf G är definierad som skärningspunkten graf över kanterna av G , där vi representerar varje kant som uppsättningen av dess två slutpunkter.
- Ett strängdiagram är skärningsdiagrammet för kurvor på ett plan .
- En graf har boxicitet k om det är skärningsdiagrammet för flerdimensionella rutor med dimension k , men inte av någon mindre dimension.
- Ett klickdiagram är korsningsdiagrammet för maximala klick i en annan graf
- Ett blockdiagram över klickträdet är korsningsdiagrammet för tvåanslutna komponenter i en annan graf
Scheinerman (1985) karaktäriserade skärningsklasserna för grafer , familjer av ändliga grafer som kan beskrivas som korsningsdiagrammen för uppsättningar som dras från en given uppsättning familj. Det är nödvändigt och tillräckligt att familjen har följande egenskaper:
- Varje inducerad subgraf av ett diagram i familjen måste också finnas i familjen.
- Varje graf som bildas från ett diagram i familjen genom att ersätta ett toppunkt med en klick måste också tillhöra familjen.
- Det finns en oändlig sekvens av grafer i familjen, var och en är en inducerad subgraf av nästa graf i sekvensen, med egenskapen att varje graf i familjen är en inducerad subgraf av en graf i sekvensen.
Om korsningsdiagramrepresentationerna har det ytterligare kravet att olika vertikaler måste representeras av olika uppsättningar, kan klikexpansionsegenskapen utelämnas.
Relaterade begrepp
En ordningsteoretisk analog till korsningsdiagrammen är inkluderingsordrarna . På samma sätt som en korsningsrepresentation av en graf märker varje toppunkt med en uppsättning så att hörn är intill om och endast om deras uppsättningar har en icke-snabb korsning, så en inkluderingsrepresentation f av en poset märker varje element med en uppsättning så att för alla x och y i poset, x ≤ y om och endast om f ( x ) ⊆ f ( y ).
Se även
Referenser
- Čulík, K. (1964), "Applications of graph theory to mathematical logic and linguistics", Theory of Graphs and its Applications (Proc. Sympos. Smolenice, 1963) , Prag: Publ. Hus Tjeckoslovakiska Acad. Sci., S. 13–20, MR 0176940.
- Erdős, Paul ; Goodman, AW; Pósa, Louis (1966), "Representationen av en graf med uppsatta korsningar" (PDF) , Canadian Journal of Mathematics , 18 (1): 106–112, doi : 10.4153 / CJM-1966-014-3 , MR 0186575.
- Golumbic, Martin Charles (1980), algoritmisk grafteori och perfekta grafer , Academic Press, ISBN 0-12-289260-7.
- McKee, Terry A .; McMorris, FR (1999), Topics in Intersection Graph Theory , SIAM Monographs on Discrete Mathematics and Applications, 2 , Philadelphia: Society for Industrial and Applied Mathematics, ISBN 0-89871-430-3, MR 1672910.
- Szpilrajn-Marczewski, E. (1945), "Sur deux propriétés des classes d'ensembles", Fund. Matematik. , 33 : 303–307, MR 0015448.
- Schaefer, Marcus (2010), "Complexity of some geometric and topological problems" (PDF) , Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers , Lecture Notes in Computer Science, 5849 , Springer-Verlag, s. 334–344, doi : 10.1007 / 978-3-642-11805-0_32 , ISBN 978-3-642-11804-3.
- Scheinerman, Edward R. (1985), "Characterizing intersection classes of graphs", Discrete Mathematics , 55 (2): 185–193, doi : 10.1016 / 0012-365X (85) 90047-0 , MR 0798535.
Vidare läsning
- För en översikt av både teorin om korsningsdiagram och viktiga specialklasser av korsningsdiagram, se McKee & McMorris (1999) .
externa länkar
- Jan Kratochvíl, en videoföreläsning om korsningsdiagram (juni 2007)
- E. Prisner, en resa genom korsningslänet