Algoritma Keprimitifan Dari Suatu Digraph

Muhammad Fathoni; Hari Sumardi

doi:10.46576/wdw.v18i3.4743

Algoritma Keprimitifan Dari Suatu Digraph

Muhammad Fathoni, Hari Sumardi

Abstract

Sebuah digraf D disebut terhubung kuat jika untuk setiap dua buah node u dan v dalam D, terdapat sebuah perjalanan dari u ke v dan sebuah perjalanan dari v ke u. Sebuah digraf terhubung kuat dikatakan primitif jika ada sebuah bilangan bulat positif k sedemikian hingga untuk setiap pasangan node (u,v) ada sebuah jalan dari u ke v dengan panjang k. Matriks ketetanggaan A dari sebuah digraf D dikatakan primitif jika A^m>0, untuk sebuah bilangan bulat positif m.

Keywords

Digraf, Matriks ketetanggaan, Primitif

Full Text:

PDF (Bahasa Indonesia)

References

Beasley, L. B., & Mousley, S. (2014). k-Primitivity of digraphs. Linear Algebra and Its Applications, 449, 512–519. https://doi.org/10.1016/J.LAA.2014.02.039

Bo, Z. (2003). Exponents of primitive graphs. Australasian Journal of Combinatorics, 28(10201009), 67–72.

Brualdi, R. A., & Ryser, H. J. (1991). Combinatorial Matrix Theory. https://doi.org/10.1017/CBO9781107325708

Culik, K., Karhumaki, J., & Kari, J. (2002). A Note on Synchronized Automata and Road Coloring Problem. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2295 LNCS, 175–185. https://doi.org/10.1007/3-540-46011-X_14

Kim, B. M., Song, B. C., & Hwang, W. (2007). Primitive graphs with given exponents and minimum number of edges. Linear Algebra and Its Applications, 420(2–3), 648–662. https://doi.org/10.1016/J.LAA.2006.08.021

Langville, A.N. and Meyer, C. . (2006). Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press.

O’Mahony, O., & Quinlan, R. (2019). Exponent-critical primitive graphs and the Kronecker product. Electronic Journal of Graph Theory and Applications (EJGTA), 7(2), 329–347. https://doi.org/10.5614/EJGTA.2019.7.2.10

Schneider, H. (2002). Wielandt’s proof of the exponent inequality for primitive nonnegative matrices. Linear Algebra and Its Applications, 353(1–3), 5–10. https://doi.org/10.1016/s0024-3795(02)00414-7

Suwilo, S. (2005). ON EXPONENTS OF PRIMITIVE GRAPHS. Proceedings of ICMSA, 1(1). https://jurnal.usk.ac.id/ICMSA/article/view/2707

DOI: https://doi.org/10.46576/wdw.v18i3.4743