www.wikidata.id-id.nina.az

Teori graf Artikel ini sedang dalam perubahan besar untuk sementara waktu Untuk menghindari konflik penyuntingan dimohon

Teori graf

Artikel ini bukan mengenai grafika.

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.

Sebuah graf yang dimodelkan dari Tujuh Jembatan Königsberg.

Definisi formal

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 . 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 .

Sejarah

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. Artikel tersebut dianggap sebagai makalah pertama dalam sejarah teori graf dan penerapan praktis pertama dari topologi.

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.

Lihat pula

Topik terkait

  • Teori graf aljabaris
  • Potongan graf
  • Graf konseptual
  • Data structure
  • Struktur data himpunan terurai
  • Graf entitatif
  • Graf ekstensial
  • Aljabar graf
  • Graf automorfisme
  • Pewarnaan graf
  • Basis data graf
  • Struktur data graf
  • Penggambaran graf
  • Persamaan graf
  • Graph rewriting
  • Problem roti isi
  • Sifat graf
  • Graf bersimpangan
  • Logika graf
  • Simpul
  • Teori jaring-jaring
  • Graf kosong
  • Problem gerakan kerikil
  • Perkolasi
  • Graf sempurna
  • Graf kuantum
  • Graf sederhana acak
  • Jaringan semantik
  • Teori graf spektral
  • Graf sederhana kuat
  • Graf simetris
  • Pengurangan transitif
  • Struktur data pohon

Algoritme

Subarea

  • Algebraic graph theory
  • Geometric graph theory
  • Extremal graph theory
  • Probabilistic graph theory
  • Topological graph theory

Bidang matematika terkait

Generalisasi

  • Hipergraf
  • Kompleks abstrak yang disederhanakan

Teoris graf terkemuka

  • Noga Alon
  • Claude Berge
  • Béla Bollobás
  • John Adrian Bondy
  • Graham Brightwell
  • Maria Chudnovsky
  • Fan Chung
  • Gabriel Andrew Dirac
  • Paul Erdős
  • Leonhard Euler
  • Ralph Faudree
  • Martin Charles Golumbic
  • Ronald Graham
  • Frank Harary
  • Percy John Heawood
  • Anton Kotzig
  • Dénes Kőnig
  • László Lovász
  • U. S. R. Murty
  • Jaroslav Nešetřil
  • Alfréd Rényi
  • Gerhard Ringel
  • Neil Robertson
  • Paul Seymour
  • Endre Szemerédi
  • Robin Thomas
  • Carsten Thomassen
  • Pál Turán
  • W. T. Tutte
  • Hassler Whitney

Referensi

  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

  • Diestel, Reinhard (2016). Graph Theory (edisi ke-5). Heidelberg: Springer-Verlag. ISBN 978-3-662-53621-6. 
  • Biggs, Norman; Lloyd, E. Keith; Wilson, Robin (1986). Graph Theory, 1736-1936. New York: Clarendon Press. ISBN 9780198539162. 

Pranala luar

Buku teks online

wikipedia, wiki, buku, buku, perpustakaan, artikel, baca, unduh, gratis, unduh gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, gambar, musik, lagu, film, buku, permainan, permainan.
Tanggal penerbitan:
Artikel ini sedang dalam perubahan besar untuk sementara waktu Untuk menghindari konflik penyuntingan dimohon jangan melakukan penyuntingan selama pesan ini ditampilkan Halaman ini terakhir disunting oleh InternetArchiveBot Kontrib Log 40 hari 552 menit lalu Pesan ini dapat dihapus jika halaman ini sudah tidak disunting dalam beberapa jam Jika Anda adalah penyunting yang menambahkan templat ini harap diingat untuk menghapusnya setelah selesai atau menggantikannya dengan Under construction di antara masa masa menyunting Anda Artikel ini bukan mengenai grafika 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 Sebuah graf yang dimodelkan dari Tujuh Jembatan Konigsberg Daftar isi 1 Definisi formal 2 Sejarah 3 Lihat pula 3 1 Topik terkait 3 2 Algoritme 3 3 Subarea 3 4 Bidang matematika terkait 3 5 Generalisasi 3 6 Teoris graf terkemuka 4 Referensi 5 Daftar pustaka 6 Pranala luar 6 1 Buku teks onlineDefinisi formal SuntingSebuah graf G displaystyle G adalah pasangan terurut dari himpunan yang terpisah V E displaystyle V E dimana V displaystyle V adalah himpunan simpul node atau vertex dan E displaystyle E adalah himpunan sisi edge yang berlaku E x y x y V dan x y displaystyle E subseteq x y mid x y in V textrm dan x neq y Artinya anggota himpunan E displaystyle E adalah himpunan bagian berpasangan dua tak terurut dari V displaystyle V 1 Persisnya dalam teori graf jenis graf ini disebut sebagai graf sederhana tak terarah Sebagai contoh graf G V E displaystyle G V E dengan himpunan V 1 2 3 4 5 6 displaystyle V 1 2 3 4 5 6 E 1 2 1 5 2 3 3 4 4 5 5 2 4 6 displaystyle E 1 2 1 5 2 3 3 4 4 5 5 2 4 6 Sebuah himpunan simpul V displaystyle V dari graf G displaystyle G dinotasikan sebagai V G displaystyle V G sementara himpunan sisi E displaystyle E sebagai E G displaystyle E G Sejarah Sunting Diagram oleh Euler yang menunjukkan fitur utama Tujuh Jembatan Konigsberg Teori graf bermula dari kajian matematikawan Leonhard Euler atas masalah Tujuh Jembatan Konigsberg Tujuh Jembatan Konigsberg menyajikan masalah apakah bisa melintasi tujuh jembatan yang terdapat di Konigsberg 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 SuntingGaleri graf bernama Matamu melemahkanku Daftar topik teori grafTopik terkait Sunting Teori graf aljabaris Potongan graf Graf konseptual Data structure Struktur data himpunan terurai Graf entitatif Graf ekstensial Aljabar graf Graf automorfisme Pewarnaan graf Basis data graf Struktur data graf Penggambaran graf Persamaan graf Graph rewriting Problem roti isi Sifat graf Graf bersimpangan Logika graf Simpul Teori jaring jaring Graf kosong Problem gerakan kerikil Perkolasi Graf sempurna Graf kuantum Graf sederhana acak Jaringan semantik Teori graf spektral Graf sederhana kuat Graf simetris Pengurangan transitif Struktur data pohonAlgoritme Sunting Algoritme Bellman Ford Algoritme Dijkstra Algoritme Ford Fulkerson Algoritme Kruskal Algoritme tetangga terdekat Algoritme Prim Pencarian Depth first Pencarian Breadth firstSubarea Sunting Algebraic graph theory Geometric graph theory Extremal graph theory Probabilistic graph theory Topological graph theoryBidang matematika terkait Sunting Kombinatorika Teori grup Teori Knot Teori RamseyGeneralisasi Sunting Hipergraf Kompleks abstrak yang disederhanakanTeoris graf terkemuka Sunting Noga Alon Claude Berge Bela Bollobas John Adrian Bondy Graham Brightwell Maria Chudnovsky Fan Chung Gabriel Andrew Dirac Paul Erdos Leonhard Euler Ralph Faudree Martin Charles Golumbic Ronald Graham Frank Harary Percy John Heawood Anton Kotzig Denes Konig Laszlo Lovasz U S R Murty Jaroslav Nesetril Alfred Renyi Gerhard Ringel Neil Robertson Paul Seymour Endre Szemeredi Robin Thomas Carsten Thomassen Pal Turan W T Tutte Hassler WhitneyReferensi Sunting Diestel 2016 hlm 2 Biggs Lloyd amp Wilson 1986 hlm 2 10 Croom Fred H 2016 Principles of Topology dalam bahasa Inggris Courier Dover Publications hlm 7 ISBN 978 0 486 80154 4 Parameter url status yang tidak diketahui akan diabaikan bantuan 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 Parameter url status yang tidak diketahui akan diabaikan bantuan Daftar pustaka SuntingDiestel Reinhard 2016 Graph Theory edisi ke 5 Heidelberg Springer Verlag ISBN 978 3 662 53621 6 Parameter url status yang tidak diketahui akan diabaikan bantuan Biggs Norman Lloyd E Keith Wilson Robin 1986 Graph Theory 1736 1936 New York Clarendon Press ISBN 9780198539162 Parameter url status yang tidak diketahui akan diabaikan bantuan Pranala luar SuntingGraph theory with examples Hazewinkel Michiel ed 2001 1994 Graph theory Encyclopedia of Mathematics Springer Science Business Media B V Kluwer Academic Publishers ISBN 978 1 55608 010 4 Graph theory tutorial Diarsipkan 2012 01 16 di Wayback Machine A searchable database of small connected graphs Image gallery graphs di www nd edu Galat URL arsip tidak dikenal diarsipkan tanggal 20060206155001 Concise annotated list of graph theory resources for researchers Diarsipkan 2019 07 13 di Wayback Machine rocs a graph theory IDE The Social Life of Routers non technical paper discussing graphs of people and computers Graph Theory Software Diarsipkan 2013 03 13 di Wayback Machine tools to teach and learn graph theory Bahan Buku daring dan perpustakaan di perpustakaan Anda dan perpustakaan lain tentang graph theoryBuku teks online Sunting Phase Transitions in Combinatorial Optimization Problems Section 3 Introduction to Graphs 2006 by Hartmann and Weigt Digraphs Theory Algorithms and Applications 2007 by Jorgen Bang Jensen and Gregory Gutin Graph Theory by Reinhard Diestel Diperoleh dari https id wikipedia org w index php title Teori graf amp oldid 23780341