Wikipedia

Teori graf

kajian grafik yang struktur matematika digunakan untuk model hubungan berpasangan antarobjek
Revisi sejak 7 September 2015 07.03 oleh Yozef.g.tjandra (bicara | kontrib) (→Sedikit lebih formal)

Teori graf atau teori grafik dalam matematika dan ilmu komputer adalah cabang kajian yang mempelajari sifat-sifat "graf" atau "grafik". Ini tidak sama dengan "Grafika". Secara informal, suatu graf adalah himpunan benda-benda yang disebut "simpul" (vertex atau node) yang terhubung oleh "sisi" (edge) atau "busur" (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan "simpul") yang dihubungkan oleh garis-garis (melambangkan "sisi") atau garis berpanah (melambangkan "busur"). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan "gelang" (loop).

Gambar yang menunjukkan suatu graf dengan 6 simpul dan 7 sisi.

Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada Facebook bisa direpresentasikan dengan graf, yakni simpul-simpulnya adalah para pengguna Facebook dan ada sisi antar pengguna jika dan hanya jika mereka berteman. Perkembangan algoritma untuk menangani graf akan berdampak besar bagi ilmu komputer.

Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut graf berarah atau digraf (directed graph). Digraf dengan sisi berbobot disebut jaringan.

Jaringan banyak digunakan pada cabang praktis teori graf yaitu analisis jaringan. Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah).

Sedikit lebih formal

Suatu graf G, dinotasikan sebagai  , merupakan pasangan V dan E, di mana V merupakan himpunan tak kosong berisikan simpul pada graf tersebut dan E merupakan himpunan sisi pada graf tersebut. Secara formal, himpunan E dapat dinyatakan sebagai suatu koleksi subhimpunan berkardinalitas dua dari himpunan V, atau dalam notasi matematika  . Sebagai contoh, graf pada gambar di atas dapat dinyatakan sebagai graf   di mana   dan  .

 
Gambar dengan node yang sama dengan yang di atas, tapi merupakan digraf.

Pada digraf maka pasangan-pasangan ini merupakan pasangan terurut. Untuk menyatakan digraf (gambar kedua yang menggunakan tanda panah) kita dapat menggunakan himpunan edge sebagai berikut :

 

Dalam himpunan edge untuk digraf, urutan pasangan verteks menentukan arah dari edge tersebut.

Dalam teori graf, formalisasi ini untuk memudahkan ketika nanti harus membahas terminologi selanjutnya yang berhubungan dengan graph. Beberapa terminologi berhubungan dengan teori graf :

  • Degree atau derajat dari suatu node, jumlah edge yang dimulai atau berakhir pada node tersebut. Node 5 berderajat 3. Node 1 berderajat 2.
  • Path suatu jalur yang ada pada graph, misalnya antara 1 dan 6 ada path  
  • Cycle siklus ? path yang kembali melalui titik asal 2   kembali ke 2.
  • Tree merupakan salah satu jenis graf yang tidak mengandung cycle. Jika edge f dan a dalam digraf di atas dihilangkan, digraf tersebut menjadi sebuah tree. Jumlah edge dalam suatu tree adalah nV - 1. Dimana nV adalah jumlah vertex
  • Graf Tak Berarah (Undirected Graph) Graf G disebut graf tak berarah (undirected graph) jika setiap sisinya tidak berarah. Dengan kata lain (vi,vj)=(vj,vi)
  • Graf Berarah (Directed Graph) Graf G disebut graf berarah (directed graph) jika setiap sisinya berarah. Titik awal dari suatu sisi disebut verteks awal (initial vertex) sedangkan titik akhir dari suatu sisi disebut verteks akhir (terminal vertex). Loop pada graf adalah sisi yang verteks awal dan verteks akhirnya sama.

Sejarah

Lihat pula

Topik terkait

Algoritma

Subarea

Bidang matematika terkait

Generalisasi

Teoris graf terkemuka

Referensi

Pustaka

  • Berge, Claude (1958), Théorie des graphes et ses applications, Collection Universitaire de Mathématiques, II, Paris: Dunod . English edition, Wiley 1961; Methuen & Co, New York 1962; Russian, Moscow 1961; Spanish, Mexico 1962; Roumanian, Bucharest 1969; Chinese, Shanghai 1963; Second printing of the 1962 first English edition, Dover, New York 2001.
  • Biggs, N.; Lloyd, E.; Wilson, R. (1986), Graph Theory, 1736–1936, Oxford University Press .
  • Bondy, J.A.; Murty, U.S.R. (2008), Graph Theory, Springer, ISBN 978-1-84628-969-9 .
  • Bondy, Riordan, O.M (2003), Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed. .
  • Chartrand, Gary (1985), Introductory Graph Theory, Dover, ISBN 0-486-24775-9 .
  • Gibbons, Alan (1985), Algorithmic Graph Theory, Cambridge University Press .
  • Reuven Cohen, Shlomo Havlin (2010), Complex Networks: Structure, Robustness and Function, Cambridge University Press 
  • Golumbic, Martin (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press .
  • Harary, Frank (1969), Graph Theory, Reading, MA: Addison-Wesley .
  • Harary, Frank; Palmer, Edgar M. (1973), Graphical Enumeration, New York, NY: Academic Press .
  • Mahadev, N.V.R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, North-Holland .
  • Mark Newman (2010), Networks: An Introduction, Oxford University Press .

Pranala luar

Buku teks online

Diperoleh dari "https://wiki-indonesia.club/w/index.php?title=Teori_graf&oldid=10124553"