Grafuri neorientate

Lecția 1. Grafuri neorientate. Noțiuni de bază, reprezentări și idei de BAC

Un graf neorientat este un model matematic pentru descrierea legăturilor dintre obiecte. Legăturile nu au direcție: dacă există muchia [x,y], poți merge și din x în y și din y în x.

Notație: G = (X, U), unde X = mulțimea vârfurilor, U = mulțimea muchiilor.

La BAC: oricare muchie are extremități distincte și oricare două muchii diferă prin cel puțin una dintre extremități. Adică: fără bucle [x,x] și fără muchii duplicate.

1. Terminologie esențială

Adiacență: două vârfuri sunt adiacente dacă există muchie între ele.

Incidență: o muchie este incidență cu un vârf dacă acesta îi este extremitate. Două muchii sunt incidente dacă au o extremitate comună.

Gradul unui vârf d(x) = numărul de muchii incidente cu x = numărul de vecini ai lui x.

Vârf izolat: d(x) = 0. Vârf terminal: d(x) = 1.

Teorema sumei gradelor: în orice graf neorientat:

d(1) + d(2) + ... + d(n) = 2m

Consecințe: suma gradelor e mereu pară; numărul vârfurilor de grad impar e mereu par.

2. Reprezentări

Lista de muchii: U = {[1,2], [1,5], [2,5], [4,5]}. Directă și clară. [1,5] și [5,1] sunt aceeași muchie, nu o numeri de două ori.

Matricea de adiacență: matricea A de dimensiune n x n unde A[i][j] = 1 dacă există [i,j], altfel 0.

- matricea este simetrică
- diagonala principală conține doar 0
- suma liniei i = d(i)
- suma tuturor elementelor = 2m

Notă: Dacă matricea are 202 elemente nenule, atunci m = 202/2 = 101 muchii.

Liste de adiacență: pentru fiecare vârf, lista vecinilor săi.

3. Grafuri speciale

Graf nul: nicio muchie, toate vârfurile izolate. Cu n vârfuri are n componente conexe.

Graf complet Kn: oricare două vârfuri distincte sunt adiacente.

număr muchii: n*(n-1)/2
gradul fiecărui vârf: n-1

Notă: Dacă un graf complet are 210 muchii: n*(n-1)/2 = 210 => n*(n-1) = 420 => n = 21.

Graf regulat: toate vârfurile au același grad. Nu înseamnă neapărat complet sau conex.

Graf bipartit: vârfurile se împart în două mulțimi A și B, astfel încât orice muchie are o extremitate în A și alta în B. Nicio muchie între două vârfuri din aceeași mulțime.

Graf bipartit complet: fiecare vârf din A e legat de fiecare vârf din B.

număr muchii: |A| * |B|

Notă: Dacă A = vocale din "lista" (i, a) și B = consoane (l, s, t): max 2*3 = 6 muchii.

4. Lanț, ciclu, conexitate

Lanț: succesiune de vârfuri x1, x2, ..., xk unde oricare două consecutive sunt adiacente. Lungimea = numărul de muchii = k-1.

Lanț elementar: toate vârfurile sunt distincte. Lungimea maximă într-un graf cu n vârfuri este n-1.

Lanț elementar maxim și muchii necunoscute:

La BAC poate apărea un exercițiu în care unele muchii sunt date, altele sunt necunoscute, și se știe care este un lanț elementar de lungime maximă. Strategia:

• Scrii lanțul dat și identifici toate muchiile pe care le implică
• Verifici care dintre aceste muchii există deja în lista dată și care sunt "muchiile necunoscute"
• Verifici ca lanțul dat să fie într-adevăr de lungime maximă, adică să nu existe lanț elementar mai lung în graful cu muchiile alese
• Elimini variantele care ar crea un lanț mai lung sau care contrazic datele

Exemplu: graful are 7 noduri și 8 muchii, 6 cunoscute: [1,2],[2,5],[2,6],[2,7],[3,7],[4,7]. Lanțul elementar maxim este 3,7,4,5,2,1 (lungime 5, adică 5 muchii). Muchiile implicate de lanț:

[3,7] -- există
[7,4] -- există? nu! deci [4,7] e una dintre muchiile necunoscute
[4,5] -- există? nu! deci aceasta e a două muchie necunoscută
[5,2] -- există ([2,5])
[2,1] -- există ([1,2])

Deci cele două muchii necunoscute sunt [4,7] și [4,5].

Verific că lanțul să fie maxim: cu aceste muchii nu există lanț elementar cu mai mult de 6 vârfuri.

Verific și celelalte variante să nu producă un lanț mai lung sau să contrazică lanțul dat.

Notă: Atenție: dacă o variantă adaugă o muchie care ar crea un lanț elementar mai lung decât cel dat ca maxim, acea variantă este greșită.

Ciclu elementar: lanț în care primul vârf = ultimul, iar celelalte vârfuri sunt distincte. Lungimea minimă = 3.

Graf aciclic: nu conține niciun ciclu.

Graf conex: din orice vârf se poate ajunge în orice alt vârf printr-un lanț.

Componentă conexă: o "bucată separată" a grafului, conexă și maximală.

Graf conex           = 1 componentă conexă
Graf nul cu n vârfuri = n componente conexe

5. Graf parțial, subgraf, graf complementar

Graf parțial G1 = (X, U1) cu U1 ⊆ U: păstrăm toate vârfurile, eliminăm eventual muchii.

Graf parțial conex: un graf parțial care păstrează conexitatea grafului inițial. Ca să rămână conex, nu poți elimina o muchie dacă eliminarea ei ar deconecta graful, adică dacă muchia respectivă este punte (singura legătură între două părți ale grafului).

Cum numeri grafurile parțiale conexe:

• Identifici care muchii sunt punți (eliminarea lor deconectează graful) și care nu
• Muchiile care nu sunt punți pot fi eliminate sau păstrate liber
• Dacă sunt k muchii care nu sunt punți, numărul de grafuri parțiale conexe este 2^k
• Grafurile parțiale conexe diferite de graful dat sunt 2^k - 1

Subgraf G1 = (X1, U1) cu X1 ⊆ X: putem elimina vârfuri, iar muchiile incidente cu vârfurile eliminate dispar automat.

Notă: Diferența esențială: la graf parțial vârfurile rămân toate; la subgraf putem elimina vârfuri.

Graf complementar: aceleași vârfuri, dar muchii exact acolo unde în graful inițial nu există muchii.

6. Tipare BAC frecvente

Număr de muchii dintr-o sumă de grade:

Toate 6 noduri au d=1 => suma = 6 = 2m => m = 3 muchii => 3 componente conexe

Număr de noduri ale unui graf complet:

n*(n-1)/2 = 210 => n = 21

Muchii de eliminat ca să obții arbore:

Dacă graful conex are n vârfuri și m muchii, un arbore pe aceleași vârfuri are n-1 muchii.

muchii de eliminat = m - (n-1)

Lanț elementar maxim cu muchii necunoscute:

• Scrii muchiile implicate de lanțul dat
• Compari cu muchiile cunoscute => identifici muchiile necunoscute
• Verifici ca lanțul să fie maxim (nicio variantă să nu creeze lanț mai lung)
• Elimini variantele incorecte

Număr de grafuri parțiale conexe diferite de graful dat:

Dacă sunt k muchii care nu sunt punți:

2^k - 1

Număr de subgrafuri cu o anumită mulțime de muchii:

Dacă sunt k vârfuri libere (nu apar în mulțimea de muchii dată): numărul de subgrafuri este 2^k.

Matrice de adiacență și muchii:

număr elemente nenule = 2m => m = nenule / 2

7. Greșeli frecvente

Suma gradelor este 2m, nu m. Nu uita factorul 2.

Graful complet are n*(n-1)/2 muchii, nu n*(n-1).

Graf parțial != subgraf. La graf parțial vârfurile rămân toate.

Numărul vârfurilor de grad impar este mereu par. Dacă găsești un număr impar, ai greșit.

Lungimea unui lanț = numărul de muchii, nu de vârfuri. Un lanț cu 4 vârfuri are lungimea 3.

Nu orice muchie poate fi eliminată într-un graf parțial conex. Punțile sunt obligatorii.

La lanț elementar maxim cu muchii necunoscute: dacă o variantă adaugă o muchie care creează un lanț mai lung decât cel dat, varianta este greșită.