Krydsdiagram - Intersection graph

Et eksempel på, hvordan krydsende sæt definerer en graf.

I grafteori , et vejkryds graf er en graf, der repræsenterer mønstret af skæringspunkter af en familie af sæt . Enhver graf kan repræsenteres som en skæringsgraf, men nogle vigtige specielle klasser af grafer kan defineres af de typer sæt, der bruges til at danne en skæringsrepræsentation af dem.

Formel definition

Formelt er en skæringsdiagram G en ikke-rettet graf dannet af en familie af sæt

S _i , i = 0, 1, 2, ...

ved at skabe en vinkelspids v _i for hvert sæt S _i , og forbinder to knudepunkter v _i og v _j af en kant, når de tilsvarende to sæt har en ikke tom vejkryds, dvs.

E ( G ) = {{ v _i , v _j } | i ≠ j , S _i ∩ S _j ≠ ∅}.

Alle grafer er skæringsgrafer

Enhver ikke-rettet graf G kan repræsenteres som en skæringsgraf: for hvert toppunkt v _i af G , dann et sæt S _i bestående af de kanter, der rammer v _i ; så har to sådanne sæt et ikke-frit kryds, hvis og kun hvis de tilsvarende hjørner deler en kant. Erdős, Goodman & Pósa (1966) tilvejebringer en konstruktion, der er mere effektiv (hvilket vil sige kræver et mindre samlet antal elementer i alle sæt S _i kombineret), hvor det samlede antal sætelementer højst er n ² / 4 hvor n er antallet af hjørner i grafen. De anerkender observationen om, at alle grafer er skæringsgrafer til Szpilrajn-Marczewski (1945) , men siger at se også Čulík (1964) . Det vejkryds Antallet af en graf er det totale antal elementer i enhver skæringspunktet repræsentation af grafen.

Klasser af skæringsgrafer

Mange vigtige graffamilier kan beskrives som skæringsgrafer af mere begrænsede typer sætfamilier, for eksempel sæt afledt af en slags geometrisk konfiguration:

• En intervalgraf defineres som skæringsdiagrammet for intervaller på den rigtige linje eller af tilsluttede underbilleder af en kurvediagram .
• En ligegyldighedsgraf kan defineres som skæringsgrafen for enhedsintervaller på den rigtige linje
• En cirkulær buegraf er defineret som skæringsgrafen for buer på en cirkel .
• En polygon-cirkel graf er defineret som skæringspunktet mellem polygoner med hjørner på en cirkel.
• En karakterisering af en akkordgraf er som skæringsgrafen for forbundne underbilleder af et træ .
• En trapezgraf er defineret som skæringsgrafen for trapezider dannet af to parallelle linjer. De er en generalisering af begrebet permutationsdiagram , og de er igen et specielt tilfælde af familien af ​​komplementerne til sammenlignelighedsgrafer, der er kendt som samkomparabilitetsgrafer.
• En enhedsdiskgraf er defineret som skæringsgrafen for enhedsdiske i planet.
• En cirkelgraf er skæringsgrafen for et sæt akkorder i en cirkel.
• Den cirkel pakning sætning hedder det, at plane grafer er nøjagtig krydset grafer af familier af lukkede diske i flyet afgrænset af ikke-krydsende cirkler.
• Scheinermans formodning (nu en sætning) siger, at hver plan graf også kan repræsenteres som en skæringsgraf over linjesegmenter i planet. Imidlertid kan skæringsgrafer for linjesegmenter også være ikke-plan, og genkendelse af skæringsgrafer for linjesegmenter er komplet for den eksistentielle teori om realerne ( Schaefer 2010 ).
• Den linjegraf af en graf G er defineret som skæringspunktet graf af kanterne af G , hvor vi repræsenterer hver kant som sættet af dens to endepunkter.
• En strenggraf er skæringsgrafen for kurver på et plan .
• En graf har boxicitet k, hvis det er skæringsgrafen for flerdimensionelle kasser med dimension k , men ikke af nogen mindre dimension.
• En klikgraf er skæringsgrafen for maksimale klik for en anden graf
• En blok graf af klike træ er skæringspunktet graf af biconnected komponenter af en anden graf

Scheinerman (1985) karakteriserede skæringsklasser af grafer , familier af endelige grafer, der kan beskrives som skæringsgraferne for sæt trukket fra en given familie af sæt. Det er nødvendigt og tilstrækkeligt, at familien har følgende egenskaber:

• Hvert induceret underbillede af en graf i familien skal også være i familien.
• Hver graf dannet ud fra en graf i familien ved at erstatte et toppunkt med en klik skal også tilhøre familien.
• Der findes en uendelig rækkefølge af grafer i familien, som hver er en induceret undergraf af den næste graf i sekvensen med den egenskab, at hver graf i familien er en induceret undergraf af en graf i sekvensen.

Hvis skæringsdiagramrepræsentationer har det yderligere krav, at forskellige hjørner skal repræsenteres af forskellige sæt, kan klikeekspansionsegenskaben udelades.

Relaterede begreber

En ordre-teoretisk analog til skæringsgraferne er inklusionsordren . På samme måde som en skæringsrepræsentation af en graf markerer hvert hjørne med et sæt, så at hjørner er tilstødende, hvis og kun hvis deres sæt har et uhensigtsmæssigt skæringspunkt, så en inkluderingsrepræsentation f af en poset markerer hvert element med et sæt, så det for enhver x og y i poset, x  ≤  y hvis og kun hvis f ( x ) ⊆  f ( y ).

Se også

• Kontaktgraf

Referencer

• Č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 Tjekkoslovakiske Acad. Sci., S. 13–20, MR  0176940.
• Erdős, Paul ; Goodman, AW; Pósa, Louis (1966), "Repræsentationen af ​​en graf ved at sætte kryds" (PDF) , Canadian Journal of Mathematics , 18 (1): 106–112, doi : 10.4153 / CJM-1966-014-3 , MR  0186575.
• Golumbic, Martin Charles , algoritmisk grafteori og perfekte 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), "Kompleksitet af nogle geometriske og topologiske problemer" (PDF) , Graftegning, 17. internationale symposium, GS 2009, Chicago, IL, USA, september 2009, Reviderede papirer , Forelæsningsnotater i datalogi, 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), "Karakteriserende krydsningsklasser af grafer", Diskret matematik , 55 (2): 185–193, doi : 10.1016 / 0012-365X (85) 90047-0 , MR  0798535.

Yderligere læsning

• For en oversigt over både teorien om skæringsgrafer og vigtige specielle klasser af skæringsgrafer, se McKee & McMorris (1999) .

eksterne links

• Jan Kratochvíl, En videoforelæsning om krydsningsgrafer (juni 2007)
• E. Prisner, en rejse gennem krydset County County