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:
- 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])
- 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.