Graf lengkap

Graf lengkap yang terdiri atas 7 buah verteks, Templat:Math.

Dalam teori graf, graf lengkap atau grap komplit (Templat:Lang-en) 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 (Templat:Lang-en).

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.

Sifat

Graf lengkap atau graf komplit yang terdiri atas Templat:Mvar buah verteks dinyatakan dengan lambang Templat:Mvar. Ada sumber yang mengatakan bahwa huruf Templat:Mvar pada notasi tersebut diambil dari kata dalam bahasa Jerman Templat:Lang,. Akan tetapi, dalam bahasa Jerman yang menyebutkan graf itu Templat:Lang, tidak mengandung huruf Templat:Mvar. Ada sumber lain yang mengatakan bahwa huruf pada notasi itu digunakan untuk menghormati Kazimierz Kuratowski karena telah berkontribusi dalam cabang teori graf.

Templat:Mvar memiliki Templat:Math sisi, suatu bilangan segitiga; dan juga merupakan graf beraturan dengan derajat Templat:Math. Semua graf lengkap memiliki clique maksimum tersendiri. Graf ini terhubung dengan maksimum karena Templat:Ill yang hanya tak menghubungkan graf adalah kumpulan verteks lengkap. Komplemen dari graf lengkap adalah graf kosong.

Templat:Mvar dapat didekomposisikan menjadi Templat:Mvar pohon Templat:Mvar sehingga Templat:Mvar mempunyai Templat:Mvar buah verteks. Konjektur Ringel mengatakan bahwa graf lengkap Templat:Math dapat didekomposisikan menjadi salinan dari sebarang pohon dengan Templat:Mvar sisi. Pernyataan dari konjektur ini benar untuk Templat:Mvar yang cukup besar.

Jumlah dari semua lintasan yang berbeda antara pasangan verteks khusus di dalam Templat:Math dirumuskan sebagai $$w_{n+2}=n!e_n=\lfloor en!\rfloor ,$$ dengan Templat:Mvar adalah konstanta Euler yang bernilai kira-kira sama dengan 2,7182818..., dan $$e_n=\sum _{k=0}^n\frac{1}{k!}.$$

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, ... Templat:OEIS.

Bilangan-bilangan ini memberikan nilai dari indeks Hosoya terbesar yang mungkin untuk graf dengan Templat:Mvar buah verteks. Jumlah matching sempurna graf lengkap Templat:Mvar (dengan Templat:Mvar genap) dirumuskan sebagai faktorial berganda Templat:Math.

Geometri dan topologi

Polihedron Csaszar

Graf lengkap dengan Templat:Mvar verteks merepresentasikan sisi dari suatu Templat:Nowrap Secara geometris, Templat:Math membentuk suatu segitiga, Templat:Math membentuk tetrahedron, dan seterusnya. Polihedron Császár, polihedron tak cembung yang secara topologis berupa torus, memiliki graf lengkap Templat:Math sebagai Templat:Ill. Setiap Templat:Ill dalam empat dimensi atau lebih juga memiliki rangka lengkap (complete skeleton).

Lihat pula

• Graf bipartit lengkap, graf bipartit khusus dengan verteks dari salah satu himpunan terhubung dengan setiap verteks di himpunan lainnya.