Subgraf

Definitie:
Fie G=(V, M) un graf neorientat. Se numeşte subgraf al grafului G, graful neorientat G1=(V1,M1) unde V1⊆ V iar M1 contine toate muchiile din M care au extremitătile în V1.

Exemplu:
Fie graful neorientat: G=(V, M) unde: V={ 1,2,3,4} si M={[1,2], [2,3], [1,4]} reprezentat grafic astfel:

  1. Un exemplu de subgraf al grafului G este graful neorientat:
    G1=(V1 , M1) unde: V1={1,2,3 } ( s-a şters nodul 4)
    M1=([1,2],[2,3]} (s-a eliminat muchia [1,4])
  1. Un exemplu de subgraf al grafului G este graful neorientat:
    G1=(V1 ,M1) unde:
    V1={1,2,3,4} (s-a eliminat nodul 1)
    M1={[2,3]}(s-au eliminat muchiile [1,4], [1,2])
    reprezentat grafic astfel:

Observatie:
Fie G=(V, M) un graf neorientat. Un subgraf, al grafului G, se obtine ştergând anumite vârfuri şi odată cu acestea şi muchiile care le admit ca extremitate.

%d bloggers like this: