Graf lengkap: Perbedaan antara revisi

← Revisi sebelumnya Revisi selanjutnya →

Konten dihapus Konten ditambahkan

Sebaris

Revisi per 19 Juli 2023 05.26

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

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 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 terhadap 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 (titik potong) yang hanya tak menghubungkan graf adalah kumpulan verteks lengkap. Komplemen dari graf lengkap adalah graf kosong.

Referensi

^ 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
^ 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
^ Pirnot, Thomas L. (2000), Mathematics All Around, Addison Wesley, hlm. 154, ISBN 9780201308150 .

[1] 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

[2] 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 .

[3] Gries, David; Schneider, Fred B. (1993), A Logical Approach to Discrete Math, Springer-Verlag, hlm. 436, ISBN 0387941150

[4] Pirnot, Thomas L. (2000), Mathematics All Around, Addison Wesley, hlm. 154, ISBN 9780201308150 .

[1]

[2]

[3]

[4]

@@ Baris 1: / Baris 1: @@
 [[Berkas:Complete graph K7.svg|jmpl|right|Graf lengkap yang terdiri atas 7 buah verteks, {{math|1=''K''<sub>7</sub>}}.]]
-Dalam [[teori graf]], '''graf lengkap''' atau '''grap komplit''' ({{Lang-en|complete graph}}) adalah [[graf tak berarah]] yang [[Graf sederhana|sederhana]] dengan setiap pasangan verteks yang berbeda di graf tersebut terhubung oleh satu buah [[Sisi (teori graf)|sisi]]. [[Graf berarah]] dengan setiap pasangan verteks yang berbeda di dalamnya yang terhubung oleh suatu pasangan sisi yang unik disebut '''digraf lengkap''' ({{Lang-en|complete digraph}}).<ref>{{citation
+Dalam [[teori graf]], '''graf lengkap''' atau '''grap komplit''' ({{Lang-en|complete graph}}) adalah [[graf tak berarah]] yang [[Graf sederhana|sederhana]] dengan setiap pasangan verteks (atau titik) yang berbeda di graf tersebut terhubung oleh satu buah [[Sisi (teori graf)|sisi]]. [[Graf berarah]] dengan setiap pasangan verteks yang berbeda di dalamnya yang terhubung oleh suatu pasangan sisi yang unik disebut '''digraf lengkap''' ({{Lang-en|complete digraph}}).<ref>{{citation
  | last1 = Bang-Jensen | first1 = Jørgen
  | last2 = Gutin | first2 = Gregory
@@ Baris 14: / Baris 14: @@
  | year = 2018}}; lihat [https://books.google.com/books?id=IHJgDwAAQBAJ&pg=PA17 hlm. 17]</ref>
-Teori graf itu sendiri umumnya berawal dari karya [[Leonhard Euler]] di tahun 1736 yang membahas tentang [[Tujuh Jembatan Königsberg]]. Akan tetapi, [[Penggambaran graf|penggambaran]] graf lengkap, dengan verteksnya diletakkan pada titik sudut suatu [[poligon beraturan]], sudah ada di dalam karya [[Ramon Llull]] pada abad ke-13.<ref>{{citation|contribution=Two thousand years of combinatorics|first=Donald E.|last=Knuth|author-link=Donald Knuth|pages=7–37|title=Combinatorics: Ancient and Modern|publisher=Oxford University Press|year=2013|editor1-first=Robin|editor1-last=Wilson|editor2-first=John J.|editor2-last=Watkins |contribution-url=https://books.google.com/books?id=vj1oAgAAQBAJ&pg=PA7 |isbn=978-0191630620 }}.
+Teori graf itu sendiri umumnya berawal dari karya [[Leonhard Euler]] di tahun 1736 yang membahas tentang [[Tujuh Jembatan Königsberg]]. Akan tetapi, [[Penggambaran graf|penggambaran]] graf lengkap, dengan verteksnya diletakkan pada titik sudut suatu [[poligon beraturan]], sudah ada di dalam karya [[Ramon Llull]] pada abad ke-13.<ref>{{citation
+ |contribution = Two thousand years of combinatorics
+ | first = Donald E. | last = Knuth
+ | author-link = Donald Knuth
+ | pages = 7–37
+ | title = Combinatorics: Ancient and Modern
+ | publisher = Oxford University Press
+ | year = 2013
+ | editor1-first = Robin | editor1-last = Wilson
+ | editor2-first = John J. | editor2-last = Watkins
+ | contribution-url = https://books.google.com/books?id=vj1oAgAAQBAJ&pg=PA7
+ | isbn=978-0191630620 }}.
 </ref>
+== Sifat ==
+Graf lengkap atau graf komplit yang terdiri atas {{mvar|n}} buah verteks dinyatakan dengan lambang {{mvar|K{{sub|n}}}}. Ada sumber yang mengatakan bahwa huruf {{mvar|K}} pada notasi tersebut diambil dari kata dalam bahasa Jerman {{lang|de|komplett}},<ref>{{citation
+ | first1 = David | last1 = Gries | author1-link = David Gries
+ | first2 = Fred B. | last2 = Schneider | author2-link = Fred B. Schneider
+ | title = A Logical Approach to Discrete Math
+ | publisher = Springer-Verlag
+ | year = 1993
+ | page = 436
+ | url = https://books.google.com/books?id=ZWTDQ6H6gsUC&pg=PA436
+ | isbn = 0387941150}}
+</ref>. Akan tetapi, dalam bahasa Jerman menyebutkan graf itu, {{lang|de|vollständiger Graph}}, tidak mengandung huruf {{mvar|K}}. Ada sumber lain yang mengatakan bahwa huruf pada notasi itu digunakan untuk menghormati [[Kazimierz Kuratowski]] karena telah berkontribusi terhadap cabang teori graf.<ref>{{citation
+ | title = Mathematics All Around
+ | first = Thomas L. | last = Pirnot
+ | publisher = Addison Wesley
+ | year = 2000
+ | isbn = 9780201308150
+ | page = [https://archive.org/details/mathematicsallar0000pirn_2001/page/154 154]
+ | url = https://archive.org/details/mathematicsallar0000pirn_2001/page/154}}.</ref>
+{{mvar|K{{sub|n}}}} memiliki {{math|''n''(''n'' – 1)/2}} sisi, suatu [[bilangan segitiga]]; dan juga merupakan [[graf beraturan]] dengan [[Derajat (teori graf)|derajat]] {{math|''n'' – 1}}.  Semua graf lengkap memiliki [[Clique (teori graf)|clique maksimum]] tersendiri. Graf ini [[Keterhubungan (teori graf)|terhubung]] dengan maksimum karena [[Titik potong|''vertex cut'']] (''titik potong'') yang hanya tak menghubungkan graf adalah kumpulan verteks lengkap. [[Graf komplemen|Komplemen]] dari graf lengkap adalah [[graf kosong]].
 == Referensi ==