Macam-macam Graf Dilihat dari Lintasannya

1.      Traversable Graph

Traversable graf adalah graf yang semua rusuk-rusuknya dapat dilalui masing-masing sekali atau graf yang dapat digambar tanpa mengangkat pensil.

 

Contoh: 

Teori Euler: 

- Semua graf terhubung yang mempunyai titik ganjil maksimum dua adalah traversable. 

- Traversable lintasannya selalu dimulai dari titik ganjil pertama dan diakhiri pada titik ganjil kedua. 

 Titik ganjil adalah titik dimana rusuk yang incident/bertemu dengan titik tersebut berjumlah ganjil. 

2.      Euleurian Graph

Graf yang semua rusuknya dapat dilalui masing-masing sekali dan memiliki lintasan tertutup, artinya simpul awal sama dengan simpul akhir disebut Eulerian Graf.

 

Contoh: 

Teori Euler: Bila sebuah graf semua simpul/titiknya genap maka graf tersebut mempunyai lintasan euler. Karena graf euler dapat digambar tanpa angkat pensil maka euler graf juga merupakan traversable graf. 

 

3.      Hameltonian Graph

Hamiltonian graf adalah graf yang semua simpul-simpulnya dapat dialalui masing-masing sekali dan mempunyai lintasan tertutup, artinya simpul awal sama dengan simpul akhir.

Contoh: 

Macam-macam Graf dilihat dari strukturnya....