Graf lengkap
Dalam teori graf, graf lengkap atau grap komplit (bahasa Inggris: complete graph) adalah graf tak berarah yang sederhana dengan setiap pasangan verteks (atau titik) yang berbeda di graf tersebut terhubung oleh satu buah sisi. Graf berarah dengan setiap pasangan verteks yang berbeda di dalamnya yang terhubung oleh suatu pasangan sisi yang unik disebut digraf lengkap (bahasa Inggris: complete digraph).[1]
Teori graf itu sendiri umumnya berawal dari karya Leonhard Euler di tahun 1736 yang membahas tentang Tujuh Jembatan Königsberg. Akan tetapi, penggambaran graf lengkap, dengan verteksnya diletakkan pada titik sudut suatu poligon beraturan, sudah ada di dalam karya Ramon Llull pada abad ke-13.[2]
Sifat
suntingGraf lengkap atau graf komplit yang terdiri atas n buah verteks dinyatakan dengan lambang Kn. Ada sumber yang mengatakan bahwa huruf K pada notasi tersebut diambil dari kata dalam bahasa Jerman komplett,[3]. Akan tetapi, dalam bahasa Jerman yang menyebutkan graf itu vollständiger Graph, tidak mengandung huruf K. Ada sumber lain yang mengatakan bahwa huruf pada notasi itu digunakan untuk menghormati Kazimierz Kuratowski karena telah berkontribusi dalam cabang teori graf.[4]
Kn memiliki n(n – 1)/2 sisi, suatu bilangan segitiga; dan juga merupakan graf beraturan dengan derajat n – 1. Semua graf lengkap memiliki clique maksimum tersendiri. Graf ini terhubung dengan maksimum karena vertex cut yang hanya tak menghubungkan graf adalah kumpulan verteks lengkap. Komplemen dari graf lengkap adalah graf kosong.
Kn dapat didekomposisikan menjadi n pohon Ti sehingga Ti mempunyai i buah verteks.[5] Konjektur Ringel mengatakan bahwa graf lengkap K2n+1 dapat didekomposisikan menjadi salinan dari sebarang pohon dengan n sisi.[6] Pernyataan dari konjektur ini benar untuk n yang cukup besar.[7][8]
Jumlah dari semua lintasan yang berbeda antara pasangan verteks khusus di dalam Kn+2 dirumuskan sebagai [9] dengan e adalah konstanta Euler yang bernilai kira-kira sama dengan 2,7182818..., dan
Jumlah matching graf lengkap dinyatakan dengan bilangan telepon
- 1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... (barisan A000085 pada OEIS).
Bilangan-bilangan ini memberikan nilai dari indeks Hosoya terbesar yang mungkin untuk graf dengan n buah verteks.[10] Jumlah matching sempurna graf lengkap Kn (dengan n genap) dirumuskan sebagai faktorial berganda (n – 1)!!.[11]
Geometri dan topologi
sunting
Graf lengkap dengan n verteks merepresentasikan sisi dari suatu (n – 1)-simpleks. Secara geometris, K3 membentuk suatu segitiga, K4 membentuk tetrahedron, dan seterusnya. Polihedron Császár, polihedron tak cembung yang secara topologis berupa torus, memiliki graf lengkap K7 sebagai rangkanya.[12] Setiap politop bertetangga dalam empat dimensi atau lebih juga memiliki rangka lengkap (complete skeleton).
Lihat pula
sunting- Graf bipartit lengkap, graf bipartit khusus dengan verteks dari salah satu himpunan terhubung dengan setiap verteks di himpunan lainnya.
Referensi
sunting- ^ Bang-Jensen, Jørgen; Gutin, Gregory (2018), "Basic Terminology, Notation and Results", dalam Bang-Jensen, Jørgen; Gutin, Gregory, Classes of Directed Graphs, Springer Monographs in Mathematics, Springer International Publishing, hlm. 1–34, doi:10.1007/978-3-319-71840-8_1; lihat hlm. 17 Diarsipkan 2023-08-08 di Wayback Machine.
- ^ Knuth, Donald E. (2013), "Two thousand years of combinatorics", dalam Wilson, Robin; Watkins, John J., Combinatorics: Ancient and Modern, Oxford University Press, hlm. 7–37, ISBN 978-0191630620.
- ^ Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, hlm. 436, ISBN 0387941150, diarsipkan dari versi asli tanggal 2023-08-08, diakses tanggal 2023-07-19
- ^ Pirnot, Thomas L. (2000), Mathematics All Around, Addison Wesley, hlm. 154, ISBN 9780201308150.
- ^ Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk (2019-08-05). "Optimal packings of bounded degree trees" (PDF). Journal of the European Mathematical Society (dalam bahasa Inggris). 21 (12): 3573–3647. doi:10.4171/JEMS/909. ISSN 1435-9855. Diarsipkan dari versi asli (PDF) tanggal 2020-03-09. Diakses tanggal 2020-03-09.
- ^ Ringel, G. (1963). Theory of Graphs and its Applications. Proceedings of the Symposium Smolenice.
- ^ Montgomery, Richard; Pokrovskiy, Alexey; Sudakov, Benny (2021). "A proof of Ringel's Conjecture". Geometric and Functional Analysis. 31 (3): 663–720. arXiv:2001.02665
. doi:10.1007/s00039-021-00576-2 ..
- ^ Hartnett, Kevin, "Rainbow Proof Shows Graphs Have Uniform Parts", Quanta Magazine (dalam bahasa Inggris), diarsipkan dari versi asli tanggal 2020-02-20, diakses tanggal 2020-02-20
- ^ Hassani, M. "Cycles in graphs and derangements." Math. Gaz. 88, 123–126, 2004.
- ^ Tichy, Robert F.; Wagner, Stephan (2005), "Extremal problems for topological indices in combinatorial chemistry" (PDF), Journal of Computational Biology, 12 (7): 1004–1013, CiteSeerX 10.1.1.379.8693 , doi:10.1089/cmb.2005.12.1004, PMID 16201918, diarsipkan dari versi asli (PDF) tanggal 2017-09-21, diakses tanggal 2012-03-29 .
- ^ Callan, David (2009), A combinatorial survey of identities for the double factorial, arXiv:0906.1317 , Bibcode:2009arXiv0906.1317C.
- ^ Gardner, Martin (1988), Time Travel and Other Mathematical Bewilderments, W. H. Freeman and Company, hlm. 140, Bibcode:1988ttom.book.....G, ISBN 0-7167-1924-X
