Leikkauskaavio

Graafiteoriassa leikkausgraafi on graafi , joka edustaa joukkojen perheen leikkauskaaviota . Mikä tahansa graafi voidaan esittää leikkausgraafina, mutta joitain tärkeitä erikoisluokkia voidaan määritellä leikkausjoukkojen esittämiseen käytettyjen joukkotyyppien perusteella.

Katso McKee ja McMorris [1] yleiskatsauksen leikkausgraafiteoriasta ja tärkeistä leikkausgraafien erityisluokista .

Muodollinen määritelmä

Leikkausgraafi on suuntaamaton graafi, joka on muodostettu joukkojen perheestä

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

luomalla kullekin joukolle kärkipiste ja yhdistämällä kaksi kärkeä ja reuna, jos vastaavilla kahdella joukolla on ei-tyhjä leikkauspiste, ts. $v_{i}$ $Si}$ $v_{i}$ $v_{j}$

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

Kaikki kaaviot ovat leikkauskaavioita

Mikä tahansa suuntaamaton graafi G voidaan esittää leikkausgraafina - graafin G mille tahansa kärjelle muodostamme joukon , joka koostuu reunoista, joissa on . Kahdella tällaisella joukolla on ei-tyhjä leikkauspiste, jos ja vain, jos vastaavat kärjet kuuluvat samaan reunaan. Erdős, Goodman ja Poza [2] osoittivat tehokkaamman konstruktion (joka vaatii vähemmän alkioita kaikissa joukoissa ), jossa alkioiden kokonaismäärä joukoissa ei ylitä , missä n on graafin kärkien lukumäärä. Marchevsky [3] pani merkille heidän väitteensä, että kaikki graafit ovat leikkauskaavioita , mutta he suosittelivat myös Chulikin työn [4] tarkastelua . Kuvaajan leikkauspistemäärä on elementtien vähimmäismäärä graafin esityksissä leikkauskuvaajana. $v_{i}$ $Si}$ $v_{i}$ $Si}$ $n^{2}/4$

Leikkauskaavioiden luokat

Monia tärkeitä kaavioperheitä voidaan kuvata rajoitettujen joukkotyyppien leikkauskaavioina, kuten tietyistä geometrisista konfiguraatioista johdettuja joukkoja:

Intervallikaavio määritellään kaaviona viivan välien leikkauspisteistä tai yhdistetyistä polun aligraafista .
Ympyrän kaarikuvaaja määritellään ympyrän kaaren leikkauskuvaajaksi .
Ympyrän monikulmioiden kuvaaja määritellään kaavioksi monikulmioiden leikkauspisteistä, joiden kärjet ovat ympyrällä.
Yksi sointukaavioiden ominaisuuksista on, että ne ovat puun yhdistettyjen aligraafien leikkauskaavioita .
Puolisuunnikkaan muotoinen kuvaaja määritellään kahden yhdensuuntaisen suoran muodostamien puolisuunnikkaan leikkauspisteiden kuvaajaksi. Ne ovat yleistys permutaatiograafin käsitteelle , joka puolestaan on erityinen tapaus komplementtiperheestä vertailukelpoisuuskaavioista , joita kutsutaan yhteisvertailukaavioiksi.
Yksikköympyräkuvaaja määritellään tasossa olevien yksikköympyröiden leikkauskuvaajaksi .
Ympyrän pakkauslause sanoo, että tasograafit ovat täsmälleen tasossa olevien suljettujen disjunktoitujen (kosketus sallittu) levyjen perheiden leikkauskaavioita.
Scheinermanin arvelu (nyt lause) väittää, että mikä tahansa tasograafi voidaan esittää tason suoraosien leikkauspisteiden kuvaajana . Suoran osien leikkauspisteiden kuvaajat voivat kuitenkin olla ei-tasoisia, ja suoran segmenttien leikkauspisteiden kuvaajien tunnistus on valmis reaalilukujen olemassaolon teorialle [ 5] .
Graafin G viivagraafi määritellään graafin G reunojen leikkauskuvaajaksi , jossa jokaista reunaa pidetään kahden sen päätypisteen joukkona.
Merkkijonograafi on tason käyrien leikkauspisteiden kuvaaja .
Graafilla on kehys k , jos se on k-mittaisten moniulotteisten suorakulmioiden leikkauskuvaaja , mutta ei pienempiä mittoja.

Muunnelmia ja yleistyksiä

Leikkauskaavioiden järjestyksen teoreettiset analogit ovat sisäkkäisiä järjestyksiä . Samalla tavalla kuin leikkauskuvaajan esitys merkitsee jokaisen kärjen sille osuvien reunojen joukolla, joilla on ei-tyhjä leikkauspiste, osittain järjestetyn joukon sisäkkäisjärjestyksen f -esitys merkitsee jokaisen elementin joukolla siten, että minkä tahansa x :n ja y siinä jos ja vain jos . $x\leq y$ $f(x)\subseteq f(y)$
Hermopinnoite

Kirjallisuus

K. Culik. Graafien teoria ja sen sovellukset (Proc. Sympos. Smolenice, 1963). — Praha: Publ. Talo Tšekkoslovakian Acad. Sei., 1964, s. 13-20.
Paul Erdős, A.W. Goodman, Louis Posa. Kuvaajan esitys asetettujen leikkauspisteiden mukaan // Canadian Journal of Mathematics. - 1966. - T. 18 . - S. 106-112 . - doi : 10.4153/CJM-1966-014-3 .
Martin Charles Golumbic. Algoritminen graafiteoria ja täydelliset kuvaajat. - Academic Press, 1980. - ISBN 0-12-289260-7 .
Aiheet leikkausgrafiikkateoriassa. - 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 // Rahasto. Matematiikka. . - 1945. - T. 33 . - S. 303-307 .
Marcus Schäfer. Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, syyskuu 2009, Revised Papers . - Springer-Verlag, 2010. - Voi. 5849. - S. 334-344. — (Luentomuistiinpanot tietojenkäsittelytieteestä). — ISBN 978-3-642-11804-3 . - doi : 10.1007/978-3-642-11805-0_32 .

Linkit

Jan Kratochvíl, Videoluento leikkauskaavioista (kesäkuu 2007) Arkistoitu 17. helmikuuta 2020 Wayback Machinessa
E. Prisner, A Journey through Intersection Graph County Arkistoitu 24. huhtikuuta 2021 Wayback Machinessa