Grafic Caterpillar

În teoria graficelor , un grafic omidă sau mai simplu o omidă este un copac în care toate vârfurile sunt la distanța 1 de o cale centrală.

Caracterizări echivalente

Graficele Caterpillar au fost studiate pentru prima dată într-o serie de articole de Harary și Schwenk. Numele a fost sugerat de A. Hobbs. Harary & Schwenk scriu colorat: „o omidă este un copac care se metamorfozează într-o cale atunci când coconul său de puncte finale este îndepărtat”. Graficele omizi au o etichetare grațioasă .

Următoarele caracterizări descriu omizi: Omizile sunt

copaci pentru care îndepărtarea frunzelor și a marginilor incidente produce un grafic de cale .
copaci în care există o cale care conține toate vârfurile de gradul doi sau mai mult.
copaci în care fiecare vârf de grad cel puțin trei are cel mult doi vecini care nu sunt frunze.
arborii care nu conțin sub-grafic graficul obținut prin înlocuirea fiecărei muchii a graficului stelar K 1,3 cu o cale de lungime două.
grafice conectate care pot fi desenate cu vârfurile lor pe două linii paralele, cu muchii reprezentate de segmente de linii care nu se încrucișează care au un punct final pe fiecare dintre linii.
copaci al căror pătrat este un lanț hamiltonian . Cu alte cuvinte, într-o omidă, există o secvență ciclică a tuturor vârfurilor în care fiecare pereche de vârfuri consecutive este una sau două, iar copacii care nu sunt omizi nu au o astfel de succesiune. Un ciclu de acest tip poate fi obținut urmărind omida pe două linii paralele și concatenând secvența vârfurilor pe o linie cu inversa secvenței pe cealaltă linie.
copaci al căror grafic liniar conține un lanț hamiltonian ; un astfel de lanț poate fi obținut prin ordonarea marginilor într-un desen în două linii al arborelui. Mai general, numărul de muchii care trebuie adăugat graficului liniar al unui arbore arbitrar, astfel încât acesta să conțină un lanț hamiltonian (dimensiunea completării sale hamiltoniene) este egal cu numărul minim de descompuneri ale arborelui în omizi la margini disjuncte .
graficele conectate cu lățimea căii egală cu una.
în graficele interval fără triunghi și conexe.

Generalizări

Un arbore k este un grafic cordal cu exact n - k clici maxime , fiecare conținând k +1 vârfuri; într-un arbore k- care nu este el însuși o clică de vârfuri k +1, fiecare clică maximă separă graficul în două sau mai multe componente, sau altfel conține un vârf cu o singură frunză, un vârf care aparține doar cu un singur clic maxim. Un k- lanț este un k- arbre cu mai mult de două foi, iar o k - larvă este un k- arbre care pot fi descompuse într-un k- lanț și k- foi, fiecare adiacente unui separator care este un k - clic k -string. În această terminologie, o 1-omidă este aceeași cu un arbore de omidă, iar k- bug-urile sunt graficele numărului de margine maxim cu lățimea căii egală cu k .

Un grafic de homar este un copac în care toate vârfurile sunt la distanța 2 de o cale centrală.

Enumerare

Omizile formează o familie de grafice pentru care se poate da o formulă exactă: pentru n ≥ 3, numărul omizilor cu n vârfuri nemarcate este:

{\ displaystyle 2 ^ {n-4} +2 ^ {\ lfloor (n-4) / 2 \ rfloor}.}

Pentru n = 1, 2, 3, ... numărul omizilor cu n vârfuri este

1, 1, 1, 2, 3, 6, 10, 20, 36, 72, 136, 272, 528, 1056, 2080, 4160, ...

Acesta este rezultatul A005418 al OEIS .

Complexitatea IT

Găsirea unei omizi care acoperă un grafic este complet NP . O problemă de optimizare legată de aceasta este Problema minimă cu Caterpillar (MSCP ), în care un grafic are două costuri asociate cu marginile sale și scopul este de a găsi un arbore omidă care să acopere graficul dat și care are cel mai mic cost total. Aici, costul omidei este definit ca suma costurilor marginilor sale, unde fiecare margine costă unul din cele două costuri atribuite pe baza rolului său de margine a unei foi sau a unei margini interne. Nu există algoritm de aproximare în f (n) pentru MSCP, cu excepția cazului în care P = NP ; aici f (n) este orice funcție calculabilă în timpul polinomial al lui n, numărul vârfurilor unui grafic.

Există un algoritm parametrizat care găsește o soluție optimă pentru MSCP în grafice cu lățimea arborelui delimitat. Astfel, problema acoperirii crawlerului și MSCP au ambii algoritmi de timp liniari, indiferent dacă graficul este un grafic plan exterior , un grafic serie-paralel sau un grafic Halin .

Aplicații

Graficele de urmărire au fost utilizate în teoria graficelor chimice pentru a reprezenta structura moleculelor de hidrocarburi aromatice . În această reprezentare, se formează o omidă în care fiecare margine corespunde unui inel de 6 carbon din structura moleculară și două margini sunt incidente la un vârf ori de câte ori inelele corespunzătoare aparțin unei secvențe de inele conectate capăt la capăt în structură. El-Basil notează: „Este uimitor faptul că aproape toate graficele care au jucat un rol important în ceea ce se numește acum teoria graficelor chimice pot fi legate de graficele omidă. „În acest context, omizile sunt cunoscute și sub numele de copaci benzenici și copaci Gutman , din activitatea lui Ivan Gutman în această zonă.

Referințe

(fr) Acest articol este preluat parțial sau în totalitate din articolul Wikipedia din limba engleză intitulat „ Arborele omid ” ( vezi lista autorilor ) .

(în) Eric W. Weisstein , „ Caterpillar Graph ” pe MathWorld
Frank Harary și Allen J. Schwenk , „ Numărul de omizi ”, Matematică discretă , vol. 6, n o 4, 1973, p. 359–365 ( DOI 10.1016 / 0012-365X (73) 90067-8 )
Sherif El-Basil , „ Aplicațiile arborilor omizi în chimie și fizică ”, Journal of Mathematical Chemistry , vol. 1, n o 2 1987, p. 153–174 ( DOI 10.1007 / BF01205666 ).
Frank Harary și Allen Schwenk , „ Copaci cu pătrat hamiltonian ”, Mathematika , vol. 18, n o 1, 1971, p. 138–140 ( DOI 10.1112 / S0025579300008494 )
Frank Harary și Allen Schwenk , „ Un nou număr de trecere pentru grafice bipartite ”, Utilitas Math. , vol. 1, 1972, p. 203–209
Arundhati Raychaudhuri , „ Numărul total al intervalului unui copac și numărul de completare hamiltonian al graficului său liniar ”, Information Processing Letters , vol. 56, nr . 6, 1995, p. 299–306 ( DOI 10.1016 / 0020-0190 (95) 00163-8 )
Andrzej Proskurowski și Jan Arne Telle, „ Clase de grafice cu modele cu interval limitat ”, Matematică discretă și informatică teoretică , vol. 3, n o 4, 1999, p. 167-176 ( HAL hal-00958935v1 ).
Jürgen Eckhoff , „ Grafice cu intervale extreme ”, Journal of Graph Theory , vol. 17, n o 1, 1993, p. 117–127 ( DOI 10.1002 / jgt.3190170112 )
(în) Eric W. Weisstein , „ Lobster Graph ” pe MathWorld .
Sherif El-Basil , „ Aplicațiile arborilor omizi în chimie și fizică ”, Journal of Mathematical Chemistry , vol. 1, n o 2 1987, p. 153–174 ( DOI 10.1007 / BF01205666 ).
Ivan Gutman , „ Proprietăți topologice ale sistemelor benzenoidiene ”, Theoretica Chimica Acta , vol. 45, nr . 4, 1977, p. 309–315 ( DOI 10.1007 / BF00554539 )
Sherif El-Basil , „Arborii Caterpillar (Gutman) în teoria graficelor chimice” , în I. Gutman și SJ Cyvin (eds), Advances in theory of Benzenoid Hydrocarbons , col. „Subiecte în chimia actuală” ( nr . 153) 1990( DOI 10.1007 / 3-540-51505-4_28 ) , p. 273–289.