Pohon-pohon rentang independen dalam graph beraturan
Completely independent spanning trees in some regular graphs
Pohon-pohon perentang T1,T2,...,Tk pada graf G disebut pohon-pohon perentang independen lengkap jika pohon-pohon perentang tersebut perpasang pisah-sisi dan pisah-titik secara internal. Fokus permasalahan dalam artikel ini adalah mencari pohon perentang independen lengkap pada graf sedemikian hingga pohon-pohon perentang tersebut pisah-sisi dan pisah-titik secara internal. Dua pohon perentang T1 dan T2 pada graf G disebut pisah-sisi, jika E(T1) ∩ E(T2) = Ø dan dua pohon perentang T1 dan T2 pada graf G disebut pisah-titik secara internal jika untuk setiap anggota himpunan V(G),PT1(u,v) ∩ PT2(u,v)={u,v}. Untuk graf beraturan 2r, seperti pada produk Kartesius graf terdapat 3 pohon-pohon perentang yang independen lengkap. Pohon-pohon perentang independen lengkap dapat diterapkan pada masalah komunikasi yang fokusnya terhadap kesalahan dalam jaringan interkoneksi.
Kata Kunci: Pohon perentang independen lengkap, pohon perentang pisah-sisi, pohon perentang pisah-titik secara internal, produk cartersius graf.
Spanning trees T1,T2,...,Tk on graph G are said to be complete independent spanning trees if the spanning trees are a pair of edge-disjoint and internally vertex-disjoint. The focus of the problem in this article is to find a complete independent spanning tree on a graph such that the spanning trees are edge-disjoint and internally vertex-disjoint. Two spanning trees and graph G are said to be edge-disjoint if E(T1) ∩ E(T2) = Ø and two spanning trees on graph G are said to be internally vertex-disjoint if for each members of the set V(G),PT1(u,v) ∩ PT2(u,v)={u,v}. For a 2r regular graph, as in the Cartesian multiplication graph, there are 3 completely independent spanning trees. Completely independent spanning trees can be applied to communication problems that focus on faults in interconnecting networks.
Keywords: completely independent spanning tree, edge-disjoint spanning tree, internally vertex-disjoint spanning tree, Cartesian multiplication graph.