Republica Algeriană Democratică ș i Populară

Ministerul Educaț iei Superioare ș i al Cercetării Ș tiinț ifice

Universitatea de Ştiinţe şi Tehnologie Houari-Boumédiène

Facultatea de Matematică

Departamentul de Cercetare Operaț ională

Grafuri Perfecte ș i Aplicaț ii

Problema Recunoaș terii Grafelor Perfecte

prezentat de:
BOULHRAM Lysa
M1-RO2MIR
lysaboulhram@[Link]

Iunie 2021
Table des matières

1 Prezentare generală 6
1.1 Concepte fundamentale ale teoriei grafurilor. 6
1.1.1 Grafic . . . . . . . . . . . . . . . . . . . . . . 6 . . .
1.1.2 Vârful adiacent 6
1.1.3 Subgrafuri ș i subgrafuri induse . . . . . . . . . . . . .7 . . .
1.1.4 Complementar unui graf 7
1.1.5 Grafuri conexe 7
1.1.6 Stabil 8
1.1.7 Clique . . . . . . . . . . . . . . . . . . . . . . 8 . . .
1.1.8 lan ț . . . . . . . . . . . . . . . . . . . . . . .8 . . .
1.1.9 ciclu . . . . . . . . . . . . . . . . . . . . . . 8. . . .
1.1.10 cord trou ș i anti-trou . . . . . . . . . . . . . . . . . . . . . . . . . . .8 .
1.1.11 Graf Complet 9
1.1.12 Arbori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Complexitate Algoritmică ș i Clasele Problemelor . . . . . . . . . . 9. . . .
1.2.1 Algoritm 9
1.2.2 Complexitatea unui Algoritm 9
1.2.3 Complexitatea unei Probleme 9
1.2.4 Clase de probleme . . . . . . . . . . . . . . . . . . . .
1.2.5 Problema recunoa ș terii grafurilor . . . . . . . . . . . . . . . .

2 Prezentare generală a grafurilor perfecte. 12

2.1 La Clasa Grafurilor Perfecte . . . . . . . . . . . . . . . . . . . . . .
2.2 Teoremele grafurilor perfecte . . . . . . . . . . . . . . . . . . . . . .
2.2.1 La Conjectura slabă a grafurilor perfecte . . . . . . . . . . . .
2.2.2 La Conjectura puternică a graficelor perfecte . . . . . . . . . . . .
2.2.3 Reconnaissance în timp polinomial a grafurilor perfecte . . . . . . .

3 Grafic triangulat 14
3.1 Ordine de eliminare simplicială . . . . . . . . . . . . . . . . . . . .
3.1.1 Vârful simplicial . . . . . . . . . . . . . . . . . . . . . .
3.2 Algoritmul de recunoa ș tere a graficelor triunghiulare . . . . . . . . . . . .
3.3 Aplica ț ie . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1 Limbaj utilizat . . . . . . . . . . . . . . . . .
3.3.2 program de recunoa ș tere a grafurilor triunghiulare . . . . . .
3.3.3 Aplica ț ie pe un Exemplu . . . . . . . . . . . . . . . . . .

2
4 grafuri fără picioare 20
4.1 Graf multiparti-complet . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1 Algoritmul de recunoa ș tere a graficelor Fără Picior . . . . . . . .
4.2 Aplica ț ie . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1 program de recunoa ș tere a graficelor fără triunghi . . . . .
4.2.2 program de recunoa ș tere a grafurilor multipartite-complete . . . .
4.2.3 program de recunoa ș tere a grafurilor fără picior . . . . . .

3
Introducere

Teoria grafurilor este un domeniu foarte vast. O folosim adesea ca instrument de modelare.
rezolvarea problemelor practice. Într-adevăr, soluț ionarea unei probleme modelate printr-un graf
revine în general la căutarea anumitor caracteristici ale graficului sau la colorarea acestuia sau chiar

a testa apartenenț a la una dintre clasele cunoscute de grafuri. Acest test pe care îl efectuezi pentru

a decide apartenenț a sau nu a unui graf la o clasă dată de grafuri este cunoscut sub
numele „recunoaș terii grafurilor”. Există mai multe clase de grafuri în literatura-
Importanț a lor rezidă în utilitatea lor în practici ș i în diversele situaț ii care
pot fi modelizate prin grafuri aparț inând acestor clase.

În primul capitol, vom introduce câteva terminologii utilizate în

un set din acest document ș i noț iunile de grafuri utile pentru a defini grafurile triunghiulare.

Vom defini ulterior clasa graficelor triunghiulare ș i vom aborda problema re-
cunoș tinț ă. În capitolul trei.
În al doilea capitol, vom vorbi despre clasa grafurilor perfecte care a fost definită
par Berge la începutul anilor 1960. Treptat, mai multe rezultate au arătat că această clasă

poseda numeroase proprietăț i bune ș i conț inea un număr mare de clase

deja existente
În capitolul trei sunt prezentate caracteristicile graficelor triunghiulare, algoritmii lor

de recunoaș tere ș i de colorare. Se găseș te de asemenea parcursul în lăț ime lexicografică

LexBFS, care este un instrument de recunoaș tere a grafurilor chordale. În cele din urmă, vom rezolva prin

baza unui program implementat în limbajul de programare python algoritmul

de recunoaș tere a graficelor din această clasă

4
 În capitolul patru, se vorbeș te despre grafurile Sns patte. Se va oferi o prezentare generală asupra

proprietăț ile cele mai importante ale acestei clase de graf. De asemenea, se vor oferi diferitele instrumente

et noț iuni folosite pentru recunoaș tere În cele din urmă, vom rezolva prin intermediul unui pro-

gramme implementat sub limbajul de programare python algoritmul de recunoaș tere

grafuri din această clasă

5
Capitolul 1

Prezentare generală

1.1 Conceptelor fundamentale ale teoriei grafurilor

1.1.1 Graf

Un graf finitG= (V,E)este definit de ansamblul finitV= v1 , v2 , ..., v nnu elementele

sunt numiț i vârfuri, ș i prin ansamblul finitE= e1 , e2 , ..., e melementele sunt numite
ariste. O arista e a ansamblului E este definită printr-o pereche neordonată de vârfuri, numite

vârfurile a ș i b sunt adiacente.

sau incidente cu e, sau că arista e este incidentă cu vârfurile a ș i b.

1.1.2 Vârf adiacent

Să fieu, v două vârfuri deG. Siuv∈ Edeciuetvsunt numiț i adiacenț i sau vecini.
Reciproc, dacăuv/∈
/ Edeciuș ivsunt numiț i non-adjacent sau non-vecini. Dacă e= uvest
o arț ă de G, atunciuș ivsunt extremităț ile dee, et e est dite incidente ‘a uș ivDoi
Ar etele sunt numite incidente dacă au o extremitate comună.

Vecinătatea unui vârfveste ansamblul vârfurilor adiacente ‘av, notatN (v).

6
1.1.3 Subgrafuri ș i subgrafuri induse

Aș adarG= (V,Eun grafic simplu. un grafic simplu H se spune subgraf deG= (V,E)si

V(H) ⊆ VetE(H) ⊆ E

Un subgrafHdeGeste graful indus deGș i vârfurile deHcare sunt adiacente în

Gei sunt înH.

FieXun ansamblu de vârfuri al grafuluiG= (V,E). Se numeș te graf indus prinXle

grafG(X) = (X, EX )défini parXș i toate are*tele deEavând extremităț ile în
XÎn special dacăG′ = (V′ ,E)este
′ un subgraf indus deG= (V,EatunciG′ = G(V′ )
Este clar că graficul indus deXeste cel mai mare subgraf deG= (V,E)contenantX.

1.1.4 Complementarul unui graf

graful complementar sau graful inversat al unui graf simpluGeste un graf simplu

G¯având aceleaș i vârfuri ș i astfel încât două vârfuri distincte deGsă fie adiacente
¯ dacă ș i
doar dacă nu sunt adiacente înG.

1.1.5 Grafuri conexe

Definiț ie :Se defineș te o relaț ie notată între vârfurile unui grafG= (V,E)dacă
sunt legate printr-un drum. Verificăm că este o relaț ie de echivalenț ă. O clasă de echivalenț ă
pentru este numită componentă conexă deGSe spune căGeste conex dacă are o singură

componente conexe. Cu alte cuvinte, un grafic G este conex dacă pentru toț i x, y din V, există

un drum în G care le leagă.

Definiț ie :FieG= (V,Eun graf conex (de ordin≥ 2). O vârfvdeGeste un
punct de articulaț ie alGș iG− veste non conex. O muchieedeGeste un pod de G ș iGe
este non conex.

7
1.1.6 Stabil

Într-un grafG= (X,Esubansamblul vârfurilorS⊂ X; S̸∅est spus stabil dacă

este constituit din vârfuri două câte două non-adjacente.

cu alte cuvinte, subgraful generat de S nu conț ine nicio muchie.

Numărul de stabilitate într-un graf, notat α(G), este cardinalul unui maxim stabil

1.1.7 Grup

O clică deG, notatK , este un ansamblu de vârfuri adiacente două câte două. Dimensiunea

o clique este egală cu numărul vârfurilor sale. O clique de Geste maxim ș i ea este de
dimensiune maximă înG.
cardinalitatea maximă a unei clique din G este notată de numărulG)

1.1.8 lan ț

O serie de G este o listă ordonată de vârfuri astfel încât fiecare vârf din listă să fie
adiacent la următorul

1.1.9 ciclu

Un ciclu este o cale închisă ale cărei margini sunt distincte.

Lungimea unei lanț uri sau a unui ciclu este numărul de muchii care o compun.

1.1.10 cordon de trou ș i anti-trou

O coardă este un arc care leagă două vârfuri non-consecutive ale unui ciclu.

Un graf cu un ciclu care are cel puț in patru vârfuri ș i ale cărui vârfuri pot fi ordonate
într-un mod care să formeze un ciclu fără sârmă.

Un anti-trou este graficele complementare ale unui trou.

8
1.1.11 Graf Complet

Un grafic este complet dacă toate vârfurile sunt adiacente între ele.
complet de ordineneste notăKn .

1.1.12 Arbori

Se numeș te arbore orice graf simpl conex fără ciclu. Se numeș te pădure orice graf simpl
fără ciclu.

1.2 Complexitate Algoritmică ș i Clasele Pro-

problemă

1.2.1 Algoritm

procedură de calcul bine definită care ia ca intrare o valoare sau un set de valori,

ș i care produce o valoare, sau un ansamblu de valori. Un algoritm este aș adar o

secvenț ă de paș i de calcul care transformă intrarea în ieș ire

1.2.2 Complexitatea unui algoritm

Complexitatea unui algoritm este o predicț ie sau o garanț ie că algoritmul nu va

nu face niciodată mai mult de un anumit număr de paș i sau operaț iuni, care depinde adesea de dimensiune

datele pe care le manipulează. În general, notăm această dimensiune cu n ș i căutăm „formula(n)” care

reprezintă numărul maxim de operaț iuni ș i depinde de algoritm.

1.2.3 Complexitatea unei Probleme

complexitatea algoritmilor a dus la o clasificare a problemelor în funcț ie de

performanț ele celor mai buni algoritmi cunoscuț i care le rezolvă.
Complexitatea unei probleme A este complexitatea celui mai bun algoritm care rezolvă A.

9
1.2.4 Clase de probleme

Defini ț ieO problemă A este reducibilă la o problemă B dacă există un algoritm

rezolvant A care utilizează un algoritm rezolvant B.

Defini ț ieDacă algoritmul care rezolvă A este polinomial, având în vedere apelurile la al său
ritmul rezolvării B ca având complexitate constantă, reducerea este numită polinomială. Se spune

că A este reducibil polinomial la B ș i se notează A B.

Clasa P

Ensemble P este ansamblul problemelor pentru care există un algoritm de rezolvare

în timp polinomial în funcț ie de dimensiunea intrărilor. Algoritmii problemelor din P

sunt consideraț i eficienț i, dar există probleme pentru care nu se cunoaș te nicio soluț ie
eficace

Clasa NP

Clasa NP (probleme Non-deterministe Polinomiale) este ansamblul problemelor care

pot fi rezolvate pe o maș ină nedeterministă în timp polinomial în funcț ie de

dimensiunea intrărilor

Clasa NP-Complet

O problemă NP-completă are proprietatea că orice problemă din NP poate fi transformată

formează în acesta într-un timp polinomial

Clasa NP-Dificilă

Acestea sunt problemele de optimizare ale căror probleme de decizie corespunzătoare sunt NP-complete.

Se conjecturează că nu există un algoritm polinomial pentru problemele de optimizare

NP-difcile. Metodele de rezolvare exacte sau aproximative propuse pe parcursul acestor

10
ultimii ani sunt numeroș i, ei sunt reflecț ia gamelor de metode de care dispunem
pentru a trata problemele de optimizare combinatorie.

1.2.5 Probleme de recunoa ș tere a graficelor

Recunoaș terea unei clase de grafuri înseamnă a oferi un algoritm care să decidă dacă
un grafic aparț ine sau nu clasei.

11
Capitolul 2

Prezentare generală a grafurilor

Parfait.

Clasa graficelor perfecte a fost definită de Berge la începutul anilor 1960. Treptat

mai multe rezultate au arătat că această clasă avea numeroase proprietăț i bune, ș i
că aceasta conț inea un număr mare de clase deja existente

2.1 La Clasa Grafurilor Perfecte

Definiț ie:Se defineș te clasa graficelor perfecte ca fiind clasa grafelor G astfel
ce pentru totH subgraf deG, aș adarω(H) = χ(H)
Un graf G se spune de Berg dacă nu conț ine nici o gaura impară, nici un anti-gaura impară ca sub-

graf indus.

2.2 Teoremele grafurilor perfecte

Grafurile perfecte, pe lângă utilitatea lor indiscutabilă în lumea algoritmicii, sunt

cunoscuț i pentru cele 3 teoreme următoare, care au fost mult timp conjecturi. Fiecare
d’eux este astăzi rezolvat:

12
2.2.1 Conjectura slabă a grafelor perfecte

Teoremă
Aș adarGun ¯
grafic perfect. AtunciGcomplementarul deGeste de asemenea perfect
Ce teoremă a fost enunț ată de Berge ș i rezolvată 12 ani mai târziu, în 1972, de Laslo Lovasz.

2.2.2 La Conjectura puternică a grafurilor perfecte

Teoremă
G este perfect dacă niciGniG ¯nu conț in găuri de lungime impară

2.2.3 Recunoa ș terea în timp polinomial a grafurilor perfecte

Teoremă
Există un algoritm terminat în timp polinomial care determină dacă un graf simpluGest
perfect sau nu.

Conjectura puternică a grafurilor perfecte ș i problema existenț ei unui algoritm de recon-

naș terea au fost rezolvate ambele în 2002 de către Seymour ș i Al.

13
Capitolul 3

Graf triunghiular

Unul dintre aspectele interesante ale grafurilor perfecte este că ele con ț in mai multe clase

fundamentele grafurilor, cum ar fi grafurile bipartite, grafurile triunghiate, grafurile

d'intervale ș i graficele de comparabilitate

În ceea ce urmează, ne vom interesa de clasa grafurilor triunghiulare, o clasă
care a găsit un loc important în practică, în special în problemele de-

locaț ie. Definim această clasă, oferind în acelaș i timp generalităț i, precum ș i algoritmul
de recunoaș tere a acestei clase de graf.
Definiț ie
Un graf este triangulat dacă tot ciclu de lungime ≥ 4conț ine o cordă (adică, graful este fără
Ckpunek≥ 4); ( adică singurele cicluri induse sunt triunghiuri.)
Exemple

Figura 3.1– -a- Graf triunghiular -b- Graf non triunghiular deoarece conț ine un ciclu
de lungime 4.

14
3.1 Ordin de eliminare simplicial

3.1.1 Vârf simplicial

Definiț ie
Un vârf x al unui graf G este spus simplicial dacă vecinătatea sa NG(x) este o clică.
Definiț ie
Un grafGà nsommets a un ordre d’élimination simplicial (PEO) dacă ș i numai dacă există un

ordine{v1 , ..., v n } vârful deG, astfel încât fiecareveueste simplu în graficele induse
prin vârfuri{v1 , ..., v n }
Teoremă (fulkerson ș i Gross)
Un graf este triangulat dacă ș i numai dacă are un ordin de eliminare simplical.

3.2 Algoritmul de recunoa ș tere a grafurilor triunghiulare

gulés

LexBFS, sau parcurgerea în lăț ime lexicografică este un algoritm din teoria grafurilor.
Este un rafinament al algoritmului de parcurs pe lăț ime (BFS pentru Breadth First Search)
în engleză). Acest parcurs este foarte util pentru a studia anumite clase de grafuri ș i pentru a obț ine

algoritmi rapizi de recunoaș tere a acestor clase.

ce algoritm permite găsirea eficientă a unui ordin de eliminare simplicială a unui graf tri-
angulat, ș i care permite prin urmare să se determine dacă un graf este triunghiular sau nu. Mai multe

algoritmii de recunoaș tere a grafurilor triunghiulare sunt bazaț i pe această idee.

15
Algoritmul 1 Algoritmul lex-BFS
Rezultat :: Un ordinσ vârfurile deG.

iniț ializare : Un grafG= (V,E)ș i un vârf de sursăs;

Pentru fiecare vârfx∈ Va face

marcax) → ∅
fin pentru

Pentrueu= na1faire:

Alegeț i un vârfxnon numerotat de marca maxima in ordinea lexicografica;

σ(eu) → x
Pentru fiecare vecin neenumeratydexa face

− marca(y) ∪ eu// Concatenare deeula finalul mărciiy

marca(y) ←
fin pentru

fin pentru

RetournerUn ordreσ deV;

Lex-BFS calculează un ordin de eliminare simplicial pentru un graf triunghiular cu o com-

complexitate temporalăO(E+ V).

Pentru a recunoaș te, aș adar, dacă un graf este triunghiat, este suficient să verifici dacă ordinea de eliminare

simplicial obț inut prin lex-BFS este perfect.

principiul algoritmului

Principiul este în linii mari de a realiza un parcurs pe lăț ime, privilegiind nodurile care
sunt cei mai puț in „văzuț i recent”.
Un pseudocod este următorul, pentru un graf cu n noduri: Iniț ial, fiecare nod are

une étiquette vide et n’a pas de numéro. pour i allant de n à 1 :

Alegeț i un vârf v care nu are număr ș i care are cea mai mare etichetă în ordine lexicografică
grafic.

Asociaț i numărul i cu v.
Pentru orice vârf adiacent lui v care nu are un număr, concatenaț i i la etichetă.

16
3.3 Aplica ț ie

3.3.1 Limbaj utilizat

Python este un limbaj de programare de nivel înalt, de uz general, utilizat pe scară largă.

A fost creat de Guido van Rossum în 1991 ș i dezvoltat de Python Software Foundation.
a fost conceput punând accent pe lizibilitatea codului, iar sintaxa sa permite programatorilor

de a-ș i exprima conceptele în mai puț ine linii de cod.

17
3.3.2 program de recunoa ș tere a graficelor triunghiulare

18
3.3.3 Aplica ț ie pe un Exemplu

Ordinul vârfurilor obț inut este:σ = Eu,A,D,T,M,C. Executarea algoritmului Lex-

BFS pe acest graf verifică că această ordine este o ordine de eliminare perfectă, ș i prin urmare, graful este

triunghiular.

Figura 3.2– Ordinea vârfurilor lui G

19
Capitolul 4

grafic fără picior

Teorema lui Olariu

Un graf G este fără picior dacă ș i numai dacă orice componentă conexă este fie fără triunghi,
deci multiparti-complet.
Corolar
Fie G un graf conex de Berge. G este fără lame dacă ș i numai dacă G este fie bipartit, fie
multiparti-complet.

4.1 Graf complet multiparti

Această clasă de grafuri, generalizând grafurile bipartite complete, este definită după cum urmează:

Un grafG= (V,E)este dit multiparti-complet si Vadmite o partitură înpgrajduri

S1,S2, ..., Sp , aș a cum pentrueu= 1, 2, ..., p, orice vârf de Si este adiacent oricărui vârf

deSj, pentru totj̸= eu.

Les graphes multipartis-complets sont exactement les graphes sans F, où F est le sous-graphe

engendrat de vârfurile a, b, c ș i latura ab.

RemarcăRecunoaș terea ș i colorarea optimă a grafelor multipartite-complete
sunt posibile în timp polinomial aplicând un algoritm simplu care constă în a partitiona

ner graful considerat în stabil, asigurându-vă că vârfurile aparț inând aceleaș i

20
stabile au acelaș i vecinătate.

Algoritm 2 Reconnaissance des graphs multiparti-complet

Date: Un grafic G = (V, E) cu n vârfuri.
Rezultatul: Una dintre următoarele posibilităț i: a- G nu este multiparti-complet.

b- O partiț ie minimă deGîn grajduriS1,S2, ..., S ω (uneωcolorare deG).

(1) (Iniț ializare)S:= V; Eu= 1;

(2)Atâta timp câtS ̸a face

(2.1) Alegeț i un vârfv∈ S;

(2.2)Seu:= {v} ;
(2.3) Pentru orice vârfwdeSneadjacent lava face dacăvetwau acelaș i

vecinătate înSaș adarSeu:= Seu∪ w;

Sinon întoarceGnu este multiparti-complet
(2.4)S:= S Seu;
(2.5)eu:= eu+ 1;

4.1.1 Algoritmul de recunoa ș tere a graficelor fără picior

Este uș or să descriem un algoritm polinomial de recunoaș tere a grafurilor de Berge

fără picior.

21
Algoritm 3recunoaș terea grafurilor fără picior
Date: Un graf G = (V, E) cu n vârfuri.
Rezultatul: G este fără picior sau nu

ș iGnu conț ine un triunghi

atunci grafulGeste fără picior

sauGeste multipartit-complet
alorsG est sans patte

fin si
fin algoritm

4.2 Aplica ț ie

4.2.1 program de recunoa ș tere a graficelor fără triunghiuri

22
4.2.2 program de recunoa ș tere a grafurilor multipartite-complete

4.2.3 program de recunoa ș tere a graph-urilor fără picior

23
Concluzie

Această lucrare face obiectul unei studii asupra claselor de grafuri perfecte, mai precis asupra

grafuri triunghiulare ș i grafuri fără coadă ș i proprietăț ile lor ș i generalizările după ce au
a reamintit noț iunile de bază ale teoriei grafurilor, în special anumite clase de grafuri
clasice, am menț ionat câteva teoreme despre grafuri triunghiulare.
Obiectivul acestei studii este de a face cunoscut, într-o manieră generală, conceptul de clase.

de grafuri cu diferitele lor variante, evidenț iind în acelaș i timp principalul avantaj
de la recunoaș tere a grafurilor în special în practică. Prezentând o aplicaț ie a
grafuri triunghiulare ș i am programat algoritmul de recunoaș tere a clasei grafurilor
triangulate, precum ș i algoritmul de recunoaș tere a grafurilor fără picior, aceste programe sunt

programate în Python.

24
Bibliografie

Algoritmica grafurilor, Grafuri triunghiulare, Fabien de Montgolfier

SiteISGC : https ://[Link]/.

Peter. Bartlett. Modele grafice neorientate: Grafuri cordale, Grafuri decompozabile

Arbori de intersecț ie ș i factorizări. Octombrie 2003.

[4] M. Chudnovsky ș i P.D. Seymour, algoritm de recunoa ș tere pentru grafuri Berge, preprint, 2003.

[5] Grafuri perfecte: Structură ș i algoritmi, Nicolas Trotignon.

Câteva metode de rezolvare în optimizarea combinatorie, Kherbouche Lynda,

Oubahri Zohra.

25