Lompat ke isi

Teori graf

Dari Wikipedia bahasa Indonesia, ensiklopedia bebas
Sebuah graf yang dimodelkan dari Tujuh Jembatan Königsberg.

Teori graf adalah cabang matematika dan ilmu komputer yang mempelajari graf, yaitu struktur yang menggambarkan himpunan simpul (vertex) yang beberapa di antaranya dihubungkan dengan sisi-sisi (edge), beserta propertinya.

Definisi formal

[sunting | sunting sumber]

Sebuah graf adalah pasangan terurut dari himpunan yang terpisah dimana adalah himpunan simpul (node atau vertex) dan adalah himpunan sisi (edge) yang berlaku . Artinya, anggota himpunan adalah himpunan bagian berpasangan dua tak terurut dari .[1] Persisnya dalam teori graf, jenis graf ini disebut sebagai graf sederhana tak terarah.

Sebagai contoh, graf dengan himpunan:

Sebuah himpunan simpul dari graf dinotasikan sebagai , sementara himpunan sisi sebagai .

Diagram oleh Euler yang menunjukkan fitur utama Tujuh Jembatan Königsberg.

Teori graf bermula dari kajian matematikawan Leonhard Euler atas masalah Tujuh Jembatan Königsberg. Tujuh Jembatan Königsberg menyajikan masalah apakah bisa melintasi tujuh jembatan yang terdapat di Königsberg (kini Kaliningrad, Rusia) sekali dalam berjalan terus-menerus. Pada 1736, Euler memaparkan penyelesaiannya dalam artikelnya yang berjudul Solutio problematis ad geometriam situs (Solusi dari masalah yang berkaitan dengan geometri posisi) yang menyimpulkan tidak ada solusi atas masalah tersebut.[2] Artikel tersebut dianggap sebagai makalah pertama dalam sejarah teori graf dan penerapan praktis pertama dari topologi.[3]

Lebih dari seabad setelah artikel Euler dan ketika Johann Benedict Listing memperkenalkan konsep topologi, Arthur Cayley didorong pada minat pada bentuk analitik tertentu yang muncul dari kalkulus diferensial untuk mempelajari jenis khusus graf, pohon.[4]

Lihat pula

[sunting | sunting sumber]

Topik terkait

[sunting | sunting sumber]

Algoritme

[sunting | sunting sumber]

Bidang matematika terkait

[sunting | sunting sumber]

Generalisasi

[sunting | sunting sumber]

Teoris graf terkemuka

[sunting | sunting sumber]

Referensi

[sunting | sunting sumber]
  1. ^ Diestel 2016, hlm. 2.
  2. ^ Biggs, Lloyd & Wilson 1986, hlm. 2-10.
  3. ^ Croom, Fred H. (2016). Principles of Topology (dalam bahasa Inggris). Courier Dover Publications. hlm. 7. ISBN 978-0-486-80154-4. 
  4. ^ Cayley, Arthur, ed. (1857). On the Theory of the Analytical Forms called Trees. Cambridge Library Collection - Mathematics. 3. Cambridge: Cambridge University Press. hlm. 242–246. doi:10.1017/cbo9780511703690.046. ISBN 978-0-511-70369-0. 

Daftar pustaka

[sunting | sunting sumber]

Pranala luar

[sunting | sunting sumber]

Buku teks online

[sunting | sunting sumber]