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

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

Article Metrics

Abstract view : 58 times
PDF (Bahasa Indonesia) – 35 times

Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Warta Dharmawangsa

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Jurnal Warta Dharmawangsa Terindex pada:

     

  

     

Member Of :


Diterbitkan oleh:

UNIVERSITAS DHARMAWANGSA

Alamat : Jl. K. L. Yos Sudarso No. 224 Medan
Kontak : Tel. 061 6635682 - 6613783  Fax. 061 6615190
Email   : warta@dharmawangsa.ac.id


 Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.