Bloc grafic

Un graf bloc ( arborele clică [1] ) este un tip de graf nedirecționat în care fiecare componentă (bloc) biconectată este o clică [2] .

Graficele bloc pot fi descrise prin grafice de intersecție bloc ale graficelor nedirecționate arbitrare [3] .

Descriere

Graficele bloc sunt exact acele grafice în care pentru fiecare patru vârfuri , și cele mai mari două dintre cele trei distanțe , , sunt întotdeauna [4] [5] [6] . $u$ $v$ $X$ $y$ $d(u,v)+d(x,y)$ $d(u,x)+d(v,y)$ $d(u,y)+d(v,x)$

Ele pot fi descrise și în termeni de subgrafe interzise , ca grafice care nu conțin diamante sau cicluri cu lungimea de patru sau mai mult ca subgraf generat . Adică sunt grafice de acorduri fără romburi [6] . Ele sunt, de asemenea, grafuri Ptolemeu ( grafuri cordale moștenite de distanță [7] ), în care orice două vârfuri la o distanță de doi sunt conectate printr-o singură cale cea mai scurtă [4] , și grafuri cordale, în care orice două clicuri au cel mult unul. vârf comun [4] .

Un grafic este un grafic bloc dacă și numai dacă intersecția oricăror două submulțimi conectate de vârfuri de grafic este fie goală, fie conexă. Astfel, submulțimi de vârfuri conectate dintr-un graf bloc convex formează o geometrie convexă , și niciun alt fel de graf nu are această proprietate [8] . Datorită acestei proprietăți, într-un grafic bloc conectat, orice set de vârfuri are un superset unic de conexiune minimă, închiderea mulțimii într-o geometrie convexă. Graficele bloc conectate sunt exact acele grafice în care există o cale unică generată care conectează oricare două perechi de vârfuri [1] . $G$ $G$

Clase de grafice înrudite

Graficele bloc sunt grafice cordale [9] și moștenite la distanță . Graficele moștenite de distanță sunt grafice în care oricare două căi copil între două vârfuri au aceeași lungime, ceea ce este mai slab decât cerința ca graficele bloc să aibă o singură cale copil între oricare două vârfuri. Deoarece atât graficele cordale, cât și graficele moștenite de distanță sunt subclase de grafice perfecte , graficele bloc sunt de asemenea perfecte.

Orice arbore este un grafic bloc. Mills oferă un alt exemplu de clasă de grafice bloc .

Orice bloc grafic are dreptunghiulare care nu depășește doi [10] [11] .

Graficele bloc sunt un exemplu de grafice pseudo-mediane - pentru oricare trei vârfuri, fie există un singur vârf care se află pe cele mai scurte trei căi dintre aceste trei vârfuri, fie există un singur triunghi ale cărui margini se află pe aceste căi cele mai scurte. [zece]

Graficele cu linii de arbore sunt grafice bloc în care orice vârf de tăiere este incident la cel mult două blocuri sau, echivalent, grafice bloc fără gheare . Graficele liniare ale arborilor sunt folosite pentru a găsi grafice cu un număr dat de muchii și vârfuri, în care cel mai mare subgraf generat, care este un arbore de cea mai mică dimensiune posibilă [12] .

Grafice bloc ale graficelor nedirecționate

Graficul bloc pentru un grafic dat (notat cu ) este graficul de intersecție al blocurilor din grafic : are un vârf pentru fiecare componentă biconectată a graficului și două vârfuri ale graficului sunt adiacente dacă cele două blocuri corespondente au în comun (au un comun) balama (în termenii lui Harari, un punct de articulare) [13] . Dacă este un grafic cu un vârf, atunci prin definiție va fi un grafic gol. se știe că este bloc - are o componentă bi-conectată pentru fiecare punct de articulare al graficului și fiecare componentă bi-conectată formată în acest fel va fi o clică. Invers, orice grafic bloc este un grafic pentru unele [3] . Dacă este un arbore, atunci coincide cu graficul liniare al graficului . $G$ $B(G)$ $G$ $B(G)$ $G$ $B(G)$ $K_1$ $B(K_{1})$ $B(G)$ $G$ $B(G)$ $G$ $G$ $B(G)$ $G$

Graficul are un vârf pentru fiecare punct de articulare a graficului . Două vârfuri sunt adiacente în dacă aparțin aceluiași bloc în [3] . $B(B(G))$ $G$ $B(B(G))$ $G$

Note

↑ 1 2 Kristina Vušković. Grafice fără găuri egale: un sondaj // Analiză aplicabilă și matematică discretă. - 2010. - T. 4 , nr. 2 . — S. 219–240 . - doi : 10.2298/AADM100812027V .
↑ Graficele bloc sunt uneori numite eronat arbori Husimi, după fizicianul japonez Cody Husimi ), dar Husimi considera Cactus (teoria grafurilor) - grafice în care orice componentă dublu conectată este un ciclu.
↑ 1 2 3 Frank Harary. O caracterizare a bloc-grafice // Canadian Mathematical Bulletin. - 1963. - T. 6 , nr. 1 . — S. 1–6 . - doi : 10.4153/cmb-1963-001-x .
↑ 1 2 3 Edward Howorka. Despre proprietățile metrice ale anumitor grafice de clică // Journal of Combinatorial Theory, Seria B. - 1979. - Vol. 27 , nr. 1 . — S. 67–74 . - doi : 10.1016/0095-8956(79)90069-8 .
↑ Brandstädt, Le, Spinrad, 2005 ; p. 151, Teorema 10.2.6
↑ 1 2 Hans-Jürgen Bandelt, Henry Martyn Mulder. Grafice ereditare la distanță // Journal of Combinatorial Theory, Seria B. - 1986. - V. 41 , nr. 2 . — S. 182–208 . - doi : 10.1016/0095-8956(86)90043-2 .
↑ Brandstädt, Le, Spinrad, 2005 ; pagina 130, Corolarul 8.4.2
↑ Paul H. Edelman, Robert E. Jamison. Teoria geometriilor convexe // Geometriae Dedicata. - 1985. - T. 19 , nr. 3 . — S. 247–270 . - doi : 10.1007/BF00149365 .
↑ Există următoarea ierarhie a claselor de grafice: Blocul Ptolemeu strict cordal cordal $\subset$ $\subset$ $\subset$ Brandstadt, Le, Spinrad, 2005 pp. 126, Capitolul 8.2 Alte tipuri de aciclicitate; clică și hipergrafe de vecinătate
↑ 1 2 Block Graphs Arhivat 21 noiembrie 2019 la Wayback Machine , Graph Class Hierarchy Information System
↑ Brandstädt, Le, Spinrad, 2005 p. 54, Capitolul 4.5 Boxicitatea, dimensiunea intersecției și produsul punctual
↑ Paul Erdős, Michael Saks, Vera T. Sos. Arbori maxim induși în grafice // Journal of Combinatorial Theory, Seria B. - 1986. - V. 41 , nr. 1 . — p. 61–79 . - doi : 10.1016/0095-8956(86)90028-6 .
↑ F. Harari. Teoria grafurilor. - Moscova: URSS, 2003. - ISBN 5-354-00301. Capitolul 3. Blocuri, pp. 41-46

Literatură

Andreas Brandstädt, Van Bang Le, Jeremy P. Spinrad. Clasele de grafice: un sondaj. - Philadelphia: SIAM, 2005. - (Monografii SIAM despre matematică discretă). — ISBN 0-89871-432-X .