نقش گراف‌ها با ساختار درخت در برخی گرایشهای علوم

نوع مقاله : مقاله پژوهشی

نویسندگان

1 هیات علمی، دانشکده مهندسی کامپیوتر، دانشگاه آزاد اسلامی واحد بستان آباد

2 استاد دانشکده علوم ریاضی، دانشگاه یزد، یزد، ایران

چکیده

درختان، یکی از اساسی‌ترین کلاس‌ها در گراف‌ها هستند. آن‌ها نه‌تنها نقش کلیدی در نظریه گراف و ترکیبیات دارند، بلکه در بسیاری از زمینه‌های دیگر ریاضیات و همچنین در سایر علوم مانند زیست‌شناسی، شیمی و علوم کامپیوتر نیز ظاهر می‌شوند. در این مقاله به بررسی خلاصه کاربردهای درختان در شیمی، زیست شناسی و کامپیوتر می‌پردازیم. درختان، یکی از اساسی‌ترین کلاس‌ها در گراف‌ها هستند. آن‌ها نه‌تنها نقش کلیدی در نظریه گراف و ترکیبیات دارند، بلکه در بسیاری از زمینه‌های دیگر ریاضیات و همچنین در سایر علوم مانند زیست‌شناسی، شیمی و علوم کامپیوتر نیز ظاهر می‌شوند. در این مقاله به بررسی خلاصه کاربردهای درختان در شیمی، زیست شناسی و کامپیوتر می‌پردازیم. درختان، یکی از اساسی‌ترین کلاس‌ها در گراف‌ها هستند. آن‌ها نه‌تنها نقش کلیدی در نظریه گراف و ترکیبیات دارند، بلکه در بسیاری از زمینه‌های دیگر ریاضیات و همچنین در سایر علوم مانند زیست‌شناسی، شیمی و علوم کامپیوتر نیز ظاهر می‌شوند. در این مقاله به بررسی خلاصه کاربردهای درختان در شیمی، زیست شناسی و کامپیوتر می‌پردازیم.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

The role of graphs with tree structure in some sciences

نویسندگان [English]

  • Mohammad Zeynali Azim 1
  • Saeid Alikhani 2
1 Department of Mathematical Sciences, Yazd University, Yazd, Iran
2 Department of Mathematical Sciences, Yazd University, Yazd, Iran
چکیده [English]

Trees are one of the most basic classes in graphs. They not only play a key role in the theory of graphs and combinatorics, but also in many other fields of mathematics, as well as in other sciences such as biology, chemistry, and computer science. In this article, we review the applications of trees in chemistry, biology, and computers.

کلیدواژه‌ها [English]

  • Tree
  • Chemistry
  • Computer
  • Decision
[1]  Daniel Irving Bernstein, Lam Si Tung Ho, Colby Long, Mike Steel, Katherine St. John, and Seth Sullivant, Bounds on the expected size of the maximum agreement subtree, SIAM J. Discrete Math. 29, 2015, no. 4, 2065–2074, DOI 10.1137/140997750. MR3416130
[2] Daniel Irving Bernstein, Lam Si Tung Ho, Colby Long, Mike Steel, Katherine St. John, and Seth Sullivant, Bounds on the expected size of the maximum agreement subtree, SIAM J. Discrete Math. 29, 2015, no. 4, 2065–2074, DOI 10.1137/140997750. MR3416130
[3]  Joshua Cooper, Bill Kay, and Anton Swifton, Graham’s tree reconstruction conjecture and a Waring-type problem on partitions, J. Comb. 9, 2018, no. 3, 469–488, DOI 10.4310/JOC.2018.v9.n3.a3. MR3809644
[4]  Michael Drmota, Random trees: An interplay between combinatorics and probability, SpringerWienNewYork, Vienna, 2009, DOI 10.1007/978-3-211-75357-6. MR2484382
[5]  Donald E. Knuth, The art of computer programming. Vol. 1: Fundamental algorithms, Addison-Wesley, Reading, MA, 1997. Third edition [of MR0286317]. MR3077152
[6] Alexey Markin, On the extremal maximum agreement subtree problem, Discrete Appl. Math. 285,  2020, 612–620, DOI 10.1016/j.dam.2020.07.007. MR4124794
[7]  Daniel M. Martin and Bhalchandra D. Thatte, The maximum agreement subtree problem, Discrete Appl. Math. 161, 2013, no. 13-14, 1805–1817, DOI 10.1016/j.dam.2013.02.037. MR3056987
[8]  Pratik Misra and Seth Sullivant, Bounds on the expected size of the maximum agreement subtree for a given tree shape, SIAM J. Discrete Math. 33, 2019, no. 4, 2316–2325, DOI 10.1137/18M1213695. MR4036089
[9] R. Montgomery, A. Pokrovskiy, and B. Sudakov, A proof of Ringel’s conjecture, Geom. Funct. Anal. 31, 2021, no. 3, 663–720, DOI 10.1007/s00039-021-00576-2. MR4311581
[10]  G. P\' olya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen (German), Acta Math. 68, 1937, no. 1, 145–254, DOI 10.1007/BF02546665. MR1577579
[11]  Robert Sedgewick and Philippe Flajolet, An
 introduction to the analysis of algorithms, Addison-
Wesley-Longman, 1996.
[12] Stephan Wagner and Hua Wang, Introduction to
chemical graph theory, Discrete Mathematics and its
 Applications (Boca Raton), CRC Press, Boca
 Raton, FL, 2019. MR3837106
[13] H. Wiener, Structural determination of paraffin boiling points, J. Am. Chem. Soc. 69, 1947, 17–20.