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. [ 1 ]
Definisi
Sebuah graf tak berarah G yang memiliki n simpul dapat dikatakan sebagai pohon apabila terpenuhi syarat-syarat berikut: [ 2 ]
- 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
- ^ a b Rosen, Kenneth H. (2013). Discrete Mathematics and Its Applications (dalam bahasa Inggris) (Edisi 7). New York: McGraw-Hill. ISBN 978-0-07-338309-5 . OCLC 1103788578 . Pemeliharaan CS1: Status URL ( link )
- ^ Van Dooren, Paul (Agustus 2009). "Graph Theory and Applications". Université catholique de Louvain .
|
Artikel bertopik matematika ini adalah sebuah rintisan . Anda dapat membantu Wikipedia dengan . |