Lohkokaavio

Lohkograafi ( klikkipuu [1] ) on suuntaamattoman graafin tyyppi, jossa kukin kaksinkertainen komponentti (lohko) on klikki [2] .

Lohkograafit voidaan kuvata mielivaltaisten suuntaamattomien graafien lohkoleikkauskaavioilla [ 3] .

Kuvaus

Lohkograafit ovat täsmälleen niitä kaavioita, joissa jokaiselle neljälle pisteelle , , ja kolmesta etäisyydestä kaksi suurinta , ovat aina [4] [5] [6] . $u$ $v$ $x$ $y$ ${\näyttötyyli d(u,v)+d(x,y)}$ ${\näyttötyyli d(u,x)+d(v,y)}$ ${\näyttötyyli d(u,y)+d(v,x)}$

Niitä voidaan myös kuvata kiellettyjen aligraafien avulla, kaavioina, jotka eivät sisällä timantteja tai neljän tai useamman pituisia syklejä generoituna aligraafina . Eli ne ovat sointukaavioita ilman timantteja [6] . Ne ovat myös Ptolemaiosgraafit ( sointuetäisyyden perimät graafit [7] ), joissa mitkä tahansa kaksi kahden etäisyyden päässä olevaa kärkeä on yhdistetty yhdellä lyhimmällä polulla [4] , ja sointugraafia, joissa kahdella klikkauksella on enintään yksi yhteinen kärkipiste [4] .

Graafi on lohkokaavio silloin ja vain, jos minkä tahansa kahden yhdistetyn graafin kärkien osajoukon leikkauspiste on joko tyhjä tai yhdistetty. Siten yhdistetyn lohkograafin kärkien yhdistetyt osajoukot muodostavat konveksin geometrian , eikä millään muulla graafilla ole tätä ominaisuutta [8] . Tämän ominaisuuden vuoksi yhdistetyssä lohkokaaviossa millä tahansa kärkijoukolla on ainutlaatuinen minimaalinen yhdistetty superjoukko, joukon sulkeminen kuperaan geometriaan. Yhdistetyt lohkokaaviot ovat juuri niitä kaavioita, joissa on ainutlaatuinen generoitu polku , joka yhdistää mitkä tahansa kaksi kärkiparia [1] . $G$ $G$

Aiheeseen liittyvät graafiluokat

Lohkograafit ovat sointu [9] ja etäisyyden periytyviä kuvaajia . Etäisyyden periytyneet graafit ovat kaavioita, joissa mitkä tahansa kaksi alipolkua kahden kärjen välillä ovat samanpituisia, mikä on heikompi kuin vaatimus, että lohkokaavioilla on yksi lapsipolku minkä tahansa kahden kärjen välillä. Koska sekä sointukuvaajat että etäisyyden perimät graafit ovat täydellisten kuvaajien alaluokkia , myös lohkokaaviot ovat täydellisiä.

Mikä tahansa puu on lohkokaavio. Mills tarjoaa toisen esimerkin lohkokaavioiden luokasta .

Minkä tahansa lohkokaavion suorakulmaisuus on enintään kaksi [10] [11] .

Lohkograafit ovat esimerkkejä pseudomediaaneista - millä tahansa kolmella kärjellä on joko yksi kärki, joka sijaitsee kolmella lyhimmällä polulla näiden kolmen kärjen välillä, tai on yksi kolmio, jonka reunat ovat näillä lyhimillä poluilla. [kymmenen]

Puuviivakaaviot ovat lohkokaavioita, joissa mikä tahansa leikkauspiste osuu enintään kahteen lohkoon, tai vastaavasti lohkokaavioita ilman kynsiä . Puiden viivagraafien avulla etsitään graafit, joissa on määrätty määrä reunoja ja pisteitä, joissa suurin generoitu aligraafi, joka on pienimmän mahdollisen kokoinen puu [12] .

Suuntaamattomien graafien lohkokaaviot

Tietyn graafin lohkokaavio (merkitty ) on graafin lohkojen leikkauskuvaaja : siinä on kärki kullekin graafin kaksijakoiselle komponentille ja kaksi graafin kärkeä ovat vierekkäin, jos vastaavat kaksi lohkoa jakavat (on yhteinen) sarana (Hararin termein nivelpiste) [13] . Jos on graafi, jossa on yksi kärki, niin se on määritelmän mukaan tyhjä graafi. tunnetaan lohkona - siinä on yksi bi-yhdistetty komponentti kutakin graafin nivelpistettä kohti , ja jokainen tällä tavalla muodostettu bi-yhdistetty komponentti on klikki. Kääntäen mikä tahansa lohkokaavio on graafi jollekin [3] . Jos on puu, niin se osuu yhteen kaavion viivakaavion kanssa . $G$ $B(G)$ $G$ $B(G)$ $G$ $B(G)$ $K_1$ $B(K_{1})$ $B(G)$ $G$ $B(G)$ $G$ $G$ $B(G)$ $G$

Graafilla on piste jokaiselle graafin artikulaatiopisteelle . Kaksi kärkeä ovat vierekkäin, jos ne kuuluvat samaan lohkoon kohdassa [3] . ${\näyttötyyli B(B(G))}$ $G$ ${\näyttötyyli B(B(G))}$ $G$

Muistiinpanot

↑ 1 2 Kristina Vušković. Parittomat kaaviot: Tutkimus // Sovellettava analyysi ja diskreetti matematiikka. - 2010. - T. 4 , no. 2 . — S. 219–240 . - doi : 10.2298/AADM100812027V .
↑ Lohkograafia kutsutaan joskus virheellisesti Husimi-puiksi, japanilaisen fyysikon Cody Husimi , mukaan, mutta Husimi piti kaktusta (graafiteoria) - kaavioita, joissa mikä tahansa kaksinkertaisesti kytketty komponentti on sykli.
↑ 1 2 3 Frank Harary. Lohkokaavioiden karakterisointi // Canadian Mathematical Bulletin. - 1963. - T. 6 , no. 1 . - S. 1-6 . - doi : 10.4153/cmb-1963-001-x .
↑ 1 2 3 Edward Howorka. Tiettyjen klikkauskaavioiden metrisistä ominaisuuksista // Journal of Combinatorial Theory, Series B. - 1979. - Vol. 27 , no. 1 . — S. 67–74 . - doi : 10.1016/0095-8956(79)90069-8 .
↑ Brandstädt, Le, Spinrad, 2005 ; s. 151, Lause 10.2.6
↑ 1 2 Hans-Jürgen Bandelt, Henry Martyn Mulder. Etäisyys-perinnölliset graafit // Journal of Combinatorial Theory, sarja B. - 1986. - V. 41 , no. 2 . — S. 182–208 . - doi : 10.1016/0095-8956(86)90043-2 .
↑ Brandstädt, Le, Spinrad, 2005 ; sivu 130, seuraus 8.4.2
↑ Paul H. Edelman, Robert E. Jamison. Kuperien geometrioiden teoria // Geometriae Dedicata. - 1985. - T. 19 , no. 3 . — S. 247–270 . - doi : 10.1007/BF00149365 .
↑ Graafiluokkien hierarkia on seuraava: Ptolemaios lohko tiukasti sointu sointu $\osajoukko$ $\osajoukko$ $\osajoukko$ Brandstadt, Le, Spinrad, 2005, s. 126, luku 8.2 Muut asyklisyystyypit; klikki- ja naapuruston hypergraafit
↑ 1 2 lohkokaaviota arkistoitu 21. marraskuuta 2019 Wayback Machinessa , Graph Class Hierarchy Information System
↑ Brandstädt, Le, Spinrad, 2005 s. 54, luku 4.5 Kotelo, leikkausmitta ja pistetulo
↑ Paul Erdős, Michael Saks, Vera T. Sos. Maksimiindusoidut puut kaavioissa // Journal of Combinatorial Theory, Series B. - 1986. - V. 41 , no. 1 . — s. 61–79 . - doi : 10.1016/0095-8956(86)90028-6 .
↑ F. Harari. Graafiteoria. - Moskova: URSS, 2003. - ISBN 5-354-00301. Luku 3. Blocks, s. 41-46

Kirjallisuus

Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad. Graafiset luokat: kysely. - Philadelphia: SIAM, 2005. - (SIAM-monografiat diskreetistä matematiikasta). — ISBN 0-89871-432-X .