Graf lengkap

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

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  buah verteks dinyatakan dengan lambang . Ada sumber yang mengatakan bahwa huruf  pada notasi tersebut diambil dari kata dalam bahasa Jerman ,. Akan tetapi, dalam bahasa Jerman yang menyebutkan graf itu , tidak mengandung huruf . Ada sumber lain yang mengatakan bahwa huruf pada notasi itu digunakan untuk menghormati Kazimierz Kuratowski karena telah berkontribusi dalam cabang teori graf.

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

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

Jumlah dari semua lintasan yang berbeda antara pasangan verteks khusus di dalam  dirumuskan sebagai   dengan  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, ... .

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

Geometri dan topologi 

Graf lengkap dengan  verteks merepresentasikan sisi dari suatu  Secara geometris,  membentuk suatu segitiga,  membentuk tetrahedron, dan seterusnya. Polihedron Császár, polihedron tak cembung yang secara topologis berupa torus, memiliki graf lengkap  sebagai . Setiap  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.

Referensi 

Graf beraturan
Keluarga graf parametrik