Graficul de intersecție

În teoria grafurilor, un graf de intersecție este un graf care reprezintă schema de intersecție a unei familii de mulțimi . Orice grafic poate fi reprezentat ca un grafic de intersecție, dar unele clase speciale importante pot fi definite în ceea ce privește tipurile de mulțimi utilizate pentru reprezentare ca mulțimi de intersecție.

Pentru o prezentare generală a teoriei grafurilor de intersecție și a unor clase speciale importante de grafuri de intersecție, vezi McKee și McMorris [1] .

Definiție formală

Un graf de intersecție este un graf nedirecționat format dintr-o familie de mulțimi

S_{i},i=0,1,2,...

prin crearea unui vârf pentru fiecare mulțime și conectarea a două vârfuri și a unei muchii dacă cele două mulțimi corespunzătoare au o intersecție nevidă, i.e. $v_{i}$ $Si}$ $v_{i}$ $v_{j}$

E(G)=\{\{v_{i},v_{j}\}|S_{i}\cap S_{j}\neq \emptyset \}

Toate graficele sunt grafice de intersecție

Orice grafic nedirecționat G poate fi reprezentat ca un grafic de intersecție - pentru orice vârf al graficului G , formăm o mulțime constând din muchii incidente cu . Două astfel de mulțimi au o intersecție nevidă dacă și numai dacă vârfurile corespunzătoare aparțin aceleiași muchii. Erdős, Goodman și Poza [2] au arătat o construcție mai eficientă (care necesită mai puține elemente în toate mulțimile ) în care numărul total de elemente din mulțimi nu depășește , unde n este numărul de vârfuri din grafic. Afirmația lor că toate graficele sunt grafice de intersecție a fost remarcată de Marchevsky [3] , dar ei au recomandat și să se uite la lucrarea lui Chulik [4] . Numărul de intersecții al unui grafic este numărul minim de elemente din reprezentările unui grafic ca grafic de intersecție. $v_{i}$ $Si}$ $v_{i}$ $Si}$ $n^{2}/4$

Clase de grafice de intersecție

Multe familii importante de grafice pot fi descrise ca grafice de intersecție cu tipuri limitate de mulțimi, cum ar fi mulțimi derivate din anumite configurații geometrice:

Un grafic de interval este definit ca un grafic al intersecțiilor de intervale pe o linie sau subgrafe de cale conectate .
Un grafic cu arc de cerc este definit ca un grafic de intersecție cu arc de cerc .
Graficul poligoanelor dintr-un cerc este definit ca graficul intersecțiilor poligoanelor cu vârfuri situate pe cerc.
Una dintre caracteristicile graficelor cordale este că sunt grafice de intersecție ale subgrafelor conectate ale unui arbore .
Un grafic trapezoidal este definit ca graficul intersecțiilor trapezelor formate din două drepte paralele. Ele sunt o generalizare a noțiunii de graf de permutare , care, la rândul lor, sunt un caz special al familiei de complement de grafuri de comparabilitate , cunoscute sub numele de grafuri de cocomparabilitate.
Graficul cercului unitar este definit ca graficul de intersecție a cercurilor unitare în plan.
Teorema de împachetare a cercurilor afirmă că graficele plane sunt exact graficele de intersecție ale familiilor de discuri disjunctive închise (permis de atingere) în plan.
Conjectura lui Scheinerman (acum o teoremă) afirmă că orice graf plan poate fi reprezentat ca un grafic al intersecțiilor segmentelor de dreaptă dintr-un plan. Totuși, graficele intersecțiilor segmentelor pe o dreaptă pot fi neplane, iar recunoașterea graficelor intersecțiilor segmentelor pe o dreaptă este completă pentru teoria existenței numerelor reale [5] .
Graficul liniare al unui grafic G este definit ca graficul de intersecție a muchiilor unui grafic G , unde fiecare muchie este considerată ca un set de două dintre vârfurile sale de capăt.
Un grafic cu șiruri este un grafic al intersecțiilor curbelor dintr-un plan .
Un grafic are cadrul k dacă este un grafic de intersecție de dreptunghiuri multidimensionale de dimensiunea k , dar nu dimensiuni mai mici.

Variații și generalizări

Analogii teoretici ai ordinului graficelor de intersecție sunt ordine de imbricare . În același mod în care reprezentarea graficului de intersecție etichetează fiecare vârf după mulțimea de muchii incidente cu acesta care au o intersecție nevidă, reprezentarea ordinului de imbricare f a unui set parțial ordonat etichetează fiecare element cu o mulțime astfel încât pentru orice x și y în ea dacă și numai dacă . $x\leq y$ $f(x)\subseteq f(y)$
Acoperire nervoasă

Literatură

K. Culik. Teoria graficelor și aplicațiile sale (Proc. Sympos. Smolenice, 1963). — Praga: Publ. Casa Cehoslovacă Acad. Sci., 1964, p. 13-20.
Paul Erdős, A.W. Goodman, Louis Posa. Reprezentarea unui grafic prin intersecții de set // Canadian Journal of Mathematics. - 1966. - T. 18 . - S. 106-112 . - doi : 10.4153/CJM-1966-014-3 .
Martin Charles Golumbic. Teoria graficelor algoritmice și graficele perfecte. - Academic Press, 1980. - ISBN 0-12-289260-7 .
Subiecte în teoria graficelor de intersecție. - Philadelphia: Society for Industrial and Applied Mathematics, 1999. - Vol. 2. - (SIAM Monographs on Discrete Mathematics and Applications). — ISBN 0-89871-430-3 .
E. Szpilrain-Marczewski. Sur deux propriétés des classes d'ensembles // Fund. Matematică. . - 1945. - T. 33 . - S. 303-307 .
Marcus Schaefer. Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, SUA, septembrie 2009, Revised Papers . - Springer-Verlag, 2010. - Vol. 5849. - S. 334-344. — (Note de curs în Informatică). — ISBN 978-3-642-11804-3 . - doi : 10.1007/978-3-642-11805-0_32 .

Link -uri

Jan Kratochvíl, A video lecture on intersection graphs (iunie 2007) Arhivat 17 februarie 2020 la Wayback Machine
E. Prisner, A Journey through Intersection Graph County Arhivat 24 aprilie 2021 la Wayback Machine