Macam-macam Graf dilihat dari strukturnya (Bagian 2)

5.      Graf Teratur (Regular Graphs)

Graf yang setiap simpulnya mempunyai sejumlah incident rusuk yang sama disebut graf teratur. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r. Jumlah sisi pada graf teratur adalah nr/2.

6.      Graf Bipartite (Bipartite Graph)

Graf yang simpul-simpulnya dapat dikelompokan menjadi dua, simpul-simpul dalam kelompok tak terhubung lengkap disebut bipartite graf. Graf G yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2,  sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 dan dinyatakan sebagai G(V1, V2).

    

Graf G di bawah ini adalah graf bipartit, karena simpul-simpulnya dapat dibagi menjadi V₁ = {a, b, d} dan V₂ = {c, e, f, g}