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]

Graf lengkap atau graf komplit yang terdiri atas n buah verteks dinyatakan dengan lambang K_n. 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]

K_n 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 [en] yang hanya tak menghubungkan graf adalah kumpulan verteks lengkap. Komplemen dari graf lengkap adalah graf kosong.

K_n dapat didekomposisikan menjadi n pohon T_i sehingga T_i mempunyai i buah verteks.^[5] Konjektur Ringel mengatakan bahwa graf lengkap K_2n+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 K_n+2 dirumuskan sebagai ^[9] $${\displaystyle w_{n+2}=n!e_{n}=\lfloor en!\rfloor ,}$$ dengan e adalah konstanta Euler yang bernilai kira-kira sama dengan 2,7182818..., dan $${\displaystyle 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, ... (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 K_n (dengan n genap) dirumuskan sebagai faktorial berganda (n – 1)!!.^[11]

Graf lengkap dengan n verteks merepresentasikan sisi dari suatu (n – 1)-simpleks [en]. Secara geometris, K₃ membentuk suatu segitiga, K₄ membentuk tetrahedron, dan seterusnya. Polihedron Császár, polihedron tak cembung yang secara topologis berupa torus, memiliki graf lengkap K₇ sebagai rangkanya [en].^[12] Setiap politop bertetangga [en] dalam empat dimensi atau lebih juga memiliki rangka lengkap (complete skeleton).

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