Grafuri derivate dintr-un graf:
Graful parţial;
Subgraful;
Graful complementar.
Graful parţial;
Subgraful;
Graful complementar.
Graf parţial
Definiţie: un graf parţial al grafului G este el însuşi un graf care s-a obţinut prin eliminarea unor muchii (arce) din graful G.
Exemplu : Graful parţial obținut prin eliminarea muchiei [1,2]:
Definiţie: un graf parţial al grafului G este el însuşi un graf care s-a obţinut prin eliminarea unor muchii (arce) din graful G.
Exemplu : Graful parţial obținut prin eliminarea muchiei [1,2]:
Teoremă : Numărul de grafuri parţiale ale unui graf cu m muchii (arce) este egal cu
Subgraf -un subgraf al grafului G este el însuşi sau un graf care s-a obţinut prin suprimarea din graful G a unor noduri şi a tuturor muchiilor (arcelor) incidente cu aceste noduri. Exemplu : Subgraful obținut prin eliminarea nodului 1 și a muchiilor adiacente lui:
Teoremă : Numărul de subgrafuri ale unui graf cu n noduri este egal cu
Graf complementar
Aplicații practice
1. Fie un graf G cu n vârfuri a cărui matrice se citește de la tastatură. Se citesc de la tastatură p numere întregi ce reprezintă etichetele unui graf GS și etichetele extremităților muchiilor lui. Să se verifice dacă graful GS este subgraf al grafului G. Algoritmul: Se verifică dacă: → Numărul din noduri din graful GS este mai mic sau egal cu numărul de noduri din graful G. → Etichetele grafului GS se află printre etichetele grafului G. → Între nodurile grafului GS există muchiile dintre nodurile din graful G și numai acelea. |
2. O persoană dintr-un grup se numește VIP dacă este cunoscută de cel puțin k persone. Știind care sunt cunoștințele din grup, să se afle care persoane sunt VIP-uri și în ce măsură se cunosc între ele.
Indicație: Graful cunoștințelor este un graf orientat deoarece relația “cunoaște pe” nu este reciprocă. Grupul VIP-urilor este un subgraf al grafului inițial format din persone care au gradul interior mai mare sau egal cu k. Etichetele persoanelor VIP vor fi memorate intr-un vector iar subgraful în matricea de adiacență asociată care va ilustra relațiile dintre VIP-uri. (VIP-urile se pot cunoaște sau nu între ele). |
3. Citiți din fișierul de intrare matrice_a.in matricea de adiacență a unui graf neorientat. Să se genereze subgraful obținut prin eliminarea nodului care are cei mai mulți vecini.
Soluție: Problema are aceeași soluție ca și problema precedentă, singura deosebire este în alegerea nodurilor care vor fi eliminate, și anume, vor fi eliminate nodurile care au gradul maxim. Pentru aflarea gradului unui nod putem folosi funcția grad_i, iar pentru aflarea gradului maxim, se memorează gradele nodurilor într-un vector cu n componente și se află valoarea maximă din vectorul gradelor.
4. Din grupul de n persoane între care s-au stabilit relații de prietenie, să se afișeze pentru fiecare persoană, persoanele cu care nu este în relație de prietenie.
Soluție: Se construiește graful complementar în care se caută nodurile adiacente fiecărui nod.
Soluție: Problema are aceeași soluție ca și problema precedentă, singura deosebire este în alegerea nodurilor care vor fi eliminate, și anume, vor fi eliminate nodurile care au gradul maxim. Pentru aflarea gradului unui nod putem folosi funcția grad_i, iar pentru aflarea gradului maxim, se memorează gradele nodurilor într-un vector cu n componente și se află valoarea maximă din vectorul gradelor.
4. Din grupul de n persoane între care s-au stabilit relații de prietenie, să se afișeze pentru fiecare persoană, persoanele cu care nu este în relație de prietenie.
Soluție: Se construiește graful complementar în care se caută nodurile adiacente fiecărui nod.