Graf (matematika)

Dari Wikipedia Indonesia, ensiklopedia bebas berbahasa Indonesia.

Sebuah graf dengan 6 sudut dan 7 sisi.
Sebuah graf dengan 6 sudut dan 7 sisi.

Dalam matematika dan ilmu komputer, sebuah graf adalah objek dasar pelajaran dalam teori graf. Dalam bahasa sehari-hari, sebuah graf adalah himpunan dari objek-objek yang dinamakan titik, simpul, atau sudut dihubungkan oleh penghubung yang dinamakan garis atau sisi. Dalam graf yang memenuhi syarat, dimana biasanya tidak berarah, sebuah garis dari titik A ke titik B dianggap sama dengan garis dari titik B ke titik A. Dalam graf berarah, garis tersebut memiliki arah. Pada dasarnya, sebuah graf digambarkan dengan bentuk diagram sebagai himpunan dari titik-titik (sudut atau simpul) yang digabungkan dengan kurva (garis atau sisi).

[sunting] Definisi

Teori graf memiliki definisi yang bervariasi. Di bawah ini merupakan definisi dasar graf dan strukturnya.

[sunting] Graf

Sebuah graf atau graf tidak berarah G adalah sebuah pasangan G: = (V,E) yang memenuhi kondisi:

  • V adalah sebuah himpunan, yang elemennya dinamakan sudut atau simpul
  • E adalah sebuah himpunan dari pasangan-pasangan sudut yang terpisah, yang dinamakan sisi atau garis.