Pohon (teori graf): Perbedaan antara revisi
Impor teks terkontrol dari Wikipedia bahasa Indonesia; revisi 28064114; atribusi sumber disertakan. |
Presentation V4: sitasi, referensi, Math, Wikimedia Commons, dan atribusi |
||
| Baris 1: | Baris 1: | ||
[[File:Tree_graph.svg|thumb|right|280px|Sebuah pohon berlabel dengan 6 simpul dan 5 sisi]] | |||
Istilah pohon atau ''trees'' digunakan pertama kali pada tahun 1857 oleh matematikawan Inggris [[Arthur Cayley]], ketika ia menggunakan istilah tersebut untuk menghitung jenis senyawa kimia tertentu. | Dalam [[teori graf]], sebuah '''pohon''' adalah [[Graf (matematika)|graf]] tak berarah yang setiap dua simpul (''vertice'') atau titiknya (''node'') saling terhubung melalui hanya sebuah sisi (''edge'') atau garis (''line''), dan tidak membentuk sirkuit atau putaran (asiklik). Sekumpulan pohon yang tidak saling terhubung dalam sebuah graf asiklik tak berarah diistilahkan sebagai '''hutan'''.<ref>Kenneth H. Rosen. [http://worldcat.org/oclc/1103788578 Discrete Mathematics and Its Applications]. McGraw-Hill. 2013. ISBN 978-0-07-338309-5.</ref> | ||
Istilah pohon atau ''trees'' digunakan pertama kali pada tahun 1857 oleh matematikawan Inggris [[Arthur Cayley]], ketika ia menggunakan istilah tersebut untuk menghitung jenis senyawa kimia tertentu.<ref>Kenneth H. Rosen. [http://worldcat.org/oclc/1103788578 Discrete Mathematics and Its Applications]. McGraw-Hill. 2013. ISBN 978-0-07-338309-5.</ref> | |||
== Definisi == | == Definisi == | ||
Sebuah graf tak berarah ''G'' yang memiliki ''n'' simpul dapat dikatakan sebagai pohon apabila terpenuhi syarat-syarat berikut: | Sebuah graf tak berarah ''G'' yang memiliki ''n'' simpul dapat dikatakan sebagai pohon apabila terpenuhi syarat-syarat berikut:<ref>Paul Van Dooren. ''Graph Theory and Applications''. ''Université catholique de Louvain''. Agustus 2009.</ref> | ||
* Simpul-simpul pada ''G'' saling terhubung melalui ''n'' − 1 sisi. | * Simpul-simpul pada ''G'' saling terhubung melalui ''n'' − 1 sisi. | ||
| Baris 13: | Baris 15: | ||
== Referensi == | == Referensi == | ||
<references /> | |||
== Sumber dan atribusi == | |||
Konten artikel ini diadaptasi dari [https://id.wikipedia.org/w/index.php?title=Pohon+%28teori+graf%29&oldid=28064114 Wikipedia bahasa Indonesia], revisi 28064114 (2025-10-17T11:15:20Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku. | |||
<!-- WIKI_UNISSULA_PRESENTATION_V4 --> | |||
Revisi terkini sejak 23 Agustus 2026 10.36
Dalam teori graf, sebuah pohon adalah graf tak berarah yang setiap dua simpul (vertice) atau titiknya (node) saling terhubung melalui hanya sebuah sisi (edge) atau garis (line), dan tidak membentuk sirkuit atau putaran (asiklik). Sekumpulan pohon yang tidak saling terhubung dalam sebuah graf asiklik tak berarah diistilahkan sebagai hutan.[1]
Istilah pohon atau trees digunakan pertama kali pada tahun 1857 oleh matematikawan Inggris Arthur Cayley, ketika ia menggunakan istilah tersebut untuk menghitung jenis senyawa kimia tertentu.[2]
Definisi
Sebuah graf tak berarah G yang memiliki n simpul dapat dikatakan sebagai pohon apabila terpenuhi syarat-syarat berikut:[3]
- Simpul-simpul pada G saling terhubung melalui n − 1 sisi.
- G bersifat asiklik (tidak membentuk sirkuit).
- Terdapat hanya satu sisi yang menghubungkan dua simpul.
- Penambahan sebuah sisi antara dua simpul akan membentuk tepat satu sirkuit.
- Pengurangan sebuah sebarang sisi akan memutuskan G.
Referensi
- ↑ Kenneth H. Rosen. Discrete Mathematics and Its Applications. McGraw-Hill. 2013. ISBN 978-0-07-338309-5.
- ↑ Kenneth H. Rosen. Discrete Mathematics and Its Applications. McGraw-Hill. 2013. ISBN 978-0-07-338309-5.
- ↑ Paul Van Dooren. Graph Theory and Applications. Université catholique de Louvain. Agustus 2009.
Sumber dan atribusi
Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 28064114 (2025-10-17T11:15:20Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.