\u7814\u7a76\u4e3b\u984c\uff1a\u6700\u5c0f\u751f\u6210\u6a39\u74b0\u4ea4\u96c6\u5047\u8a2d\u8b49\u660e<\/p>\n
\u64b0\u5beb\uff1a\u5b78\u751f\u738b\u99a8<\/p>\n
<\/p>\n
\u5728\u6700\u5c0f\u751f\u6210\u6a39\u74b0\u4ea4\u96c6 (Minimum Spanning Tree Cycle Intersection\uff0c\u7c21\u5beb\u70baMSTCI) \u7684\u554f\u984c\u4e2d\uff0c\u76ee\u6a19\u662f\u5728\u6240\u6709\u53ef\u80fd\u7684\u751f\u6210\u6a39\u4e2d\u627e\u5230\u5177\u6709\u6700\u5c0f\u6a39\u4ea4\u96c6\u6578 (tree intersection number) \u7684\u751f\u6210\u6a39\u3002Dubinsky\u7b49\u4eba (2021) \u6700\u8fd1\u63d0\u51fa\u4e86MSTCI\u554f\u984c\uff0c\u4e26\u8868\u660e\u661f\u5f62\u751f\u6210\u6a39 (star spanning tree)\uff0c\u5373\u5176\u4e2d\u4e00\u9ede\u548c\u5176\u4ed6\u6240\u6709\u9ede\u90fd\u76f8\u9130\u7684\u751f\u6210\u6a39\uff0c\u5728\u5b8c\u5168\u5716 (complete graph) \u4e2d\u6703\u5177\u6709\u6700\u5c0f\u7684\u6a39\u4ea4\u96c6\u6578\u3002Dubinsky\u7b49\u4eba\u63d0\u51fa\u5047\u8a2d\uff0c\u82e5\u4e00\u5716 (graph) \u70ba\u661f\u5f62\u751f\u6210\u6a39\uff0c\u5247\u6b64\u751f\u6210\u6a39\u5c07\u5177\u6709\u6700\u5c0f\u6a39\u4ea4\u96c6\u6578\u3002<\/p>\n
\u6839\u64da\u8d99\u6559\u6388\u8207\u9673\u6cef\u81fb\u540c\u5b78\u65bc2022\u5e746\u6708\u767c\u8868\u7684\u8ad6\u6587\uff0c\u5176\u4e0d\u50c5\u8b49\u5be6\u4e86\u6b64\u731c\u60f3\u6210\u7acb\uff0c\u66f4\u64f4\u5c55\u4e86\u5176\u53ef\u80fd\u6027\uff1a\u300c\u4e0d\u53ea\u662f\u5b8c\u5168\u5716\uff0c\u53ea\u8981\u4e00\u5716\u88e1\u6709\u661f\u5f62\u751f\u6210\u6a39\uff0c\u5b83\u5c31\u6709\u6700\u5c0f\u7684\u6a39\u4ea4\u96c6\u6578\u3002\u300d\u63db\u53e5\u8a71\u8aaa\uff0c\u7d66\u5b9a\u4e00\u5716G \u548c\u5176\u4e00\u751f\u6210\u6a39T\uff0c\u6bcf\u689d\u5728G \u2212 T \u7684\u908a (e) \u6703\u5728T \u222a {e} \u4e2d\u7522\u751f\u4e00\u500b\u74b0\uff0c\u5c07\u9019\u4e9b\u908a\u7a31\u4f5c\u74b0\u908a\uff0c\u800c\u8a72\u74b0\u5247\u7a31\u4f5c\u6a39\u74b0\u3002\u5169\u500b\u6a39\u74b0\u7684\u4ea4\u96c6\u70ba\u5176\u6240\u6709\u5171\u6709\u7684\u908a\u5f62\u6210\u7684\u96c6\u5408\uff0c\u82e5\u5169\u76f8\u7570\u6a39\u74b0\u7684\u4ea4\u96c6\u662f\u975e\u7a7a\u7684\uff0c\u5247\u5c07\u5176\u8996\u70ba\u4e00\u6b21\u4ea4\u96c6\uff0c\u800c\u751f\u6210\u6a39T \u7684\u6a39\u4ea4\u96c6\u6578\u70ba\u5176\u6240\u6709\u6a39\u74b0\u7684\u4ea4\u96c6\u6b21\u6578\u3002\u6700\u5c0f\u751f\u6210\u6a39\u74b0\u4ea4\u96c6\u554f\u984c\u65e8\u5728\u627e\u51fa\u5716\u7684\u6240\u6709\u751f\u6210\u6a39\u4e2d\u6a39\u4ea4\u96c6\u6578\u6700\u5c0f\u7684\u751f\u6210\u6a39\u3002Dubinsky \u7b49\u4eba\u63d0\u51fa\u4e00\u731c\u60f3\uff0c\u6b64\u731c\u60f3\u6558\u8ff0\u70ba\u82e5\u4e00\u5716\u6709\u4e00\u661f\u5f62\u751f\u6210\u6a39\uff0c\u5247\u6b64\u661f\u5f62\u751f\u6210\u6a39\u6709\u6700\u5c0f\u7684\u6a39\u4ea4\u96c6\u6578\u3002\u5728\u8ad6\u6587\u4e2d\uff0c\u8d99\u6559\u6388\u8207\u9673\u540c\u5b78\u8b49\u660e\u6b64\u731c\u60f3\uff0c\u4e26\u63a2\u8a0e\u5176\u5ef6\u4f38\u7684\u53ef\u80fd\u6027\u3002<\/p>\n
\u5728\u8a72\u8ad6\u6587\u4e2d\uff0cS_{x_*}\u70ba\u5efa\u69cb\u65b9\u5f0f\u7684\u6838\u5fc3\u90e8\u5206 (\u53ef\u53c3\u8003\u9644\u5716)\uff0c\u55ae\u4e00S_{x_*}\u5167\u7684\u8ff4\u5708\u908a\u5f7c\u6b64\u7686\u6709\u6a39\u74b0\u4ea4\u96c6 (cycle intersection)\uff0c\u800c\u4efb\u5169\u500bS_{x_i}\u548cS_{x_j}\u7684\u4ea4\u96c6\u500b\u6578\u5c0f\u65bc1\uff0c\u53ef\u4fdd\u8b49\u5728\u55ae\u4e00S_{x_*}\u5167\u8a08\u7b97\u7684\u6a39\u74b0\u4ea4\u96c6\u4e0d\u6703\u88ab\u91cd\u8907\u8a08\u7b97\u3002\u5982\u6b64\u5c31\u53ef\u85c9\u7531S_{x_*}\u5167\u90e8\u7684\u6210\u5c0d\u4ea4\u96c6n\u7e3d\u548c\uff0c\u8b49\u660e\u4efb\u4f55\u751f\u6210\u6a39 (\u6263\u6389\u5167\u90e8\u5206\u652f\u4e4b\u8ff4\u5708\u908a) \u7684\u6a39\u74b0\u4ea4\u96c6\u7e3d\u6578\u90fd\u6709\u4e00\u500b\u4e0b\u9650\uff0c\u800c\u5176\u4e0d\u6703\u4f4e\u65bc\u4efb\u4f55\u661f\u5f62\u751f\u6210\u6a39\u7684\u6a39\u74b0\u4ea4\u96c6\u7e3d\u6578\u3002\u7531\u6b64\uff0c\u8d99\u6559\u6388\u8207\u9673\u540c\u5b78\u8b49\u5be6Dubinsky\u7b49\u4eba\u6240\u63d0\u51fa\u7684\u731c\u60f3\uff0c\u82e5\u4e00\u5716\u6709\u4e00\u661f\u5f62\u751f\u6210\u6a39\uff0c\u5373\u5176\u4e2d\u4e00\u9ede\u548c\u5176\u4ed6\u6240\u6709\u9ede\u90fd\u76f8\u9130\u7684\u751f\u6210\u6a39\uff0c\u5247\u6b64\u661f\u5f62\u751f\u6210\u6a39\u6709\u6700\u5c0f\u7684\u6a39\u4ea4\u96c6\u6578\u3002<\/p>\n
<\/p>\n
In the Minimum Spanning Tree Cycle Intersection (MSTCI) problem, the objective is to find a spanning tree with minimum tree intersection number among all possible spanning trees. Dubinsky et al. (2021) proposed the MSTCI problem recently and showed that a star spanning tree, which is a spanning tree with one vertex connecting to all other vertices, has the minimum tree intersection number in complete graphs. Dubinsky et al. proposed that, if a graph admits a star spanning tree, then the star spanning tree has the minimum tree intersection number.<\/p>\n
According to the paper published by Prof. Kun-Mao Chao and Min-Jen Chen in June 2022, it not only confirms this conjecture, but also expands its possibilities: \u201cNot only the complete graph, but whenever a graph has a star spanning tree, it has the minimum tree intersection number.\u201d In other words, given a graph G and T be a spanning tree of G. Every edge e in G \u2212 T induces a cycle in T \u222a {e}, which is called cycle-edges, while the cycle induced by a cycle-edge is called a tree-cycle. The intersection of two tree-cycles is the set of all edges in common. If the intersection of two different tree-cycles is non-empty, it is considered as one intersection, and the number of tree intersections of the spanning tree T is the number of intersections of all its tree-cycles. MSTCI problem is aim to find a spanning tree with minimum tree intersection number among all possible spanning trees. Dubinsky et al. proposed a conjecture which states that if a graph has a star spanning tree, then this spanning tree has the minimum number of tree intersections. In the paper, Prof. Chao and Chen prove this conjecture and explore the possibility of its extension.<\/p>\n
In this paper, S_{x_*} is the core part of the construction approach (see the attached figure). The loop edges in a single S_{x_*} have cycle intersections with each other, and the intersection of any two S_{x_i} and S_{x_j} is less than 1, which ensures that the intersection of tree-cycles computed in a single S_{x_*} will not be computed repeatedly. By summing the pairwise intersections within S_{x_*}, it can be proved that the total number of intersections of any tree-cycle (minus the inter-branch loop edge) has a lower bound, and it is not lower than the total number of cycle intersections of any star spanning tree. As a result, Prof. Chao and Chen confirmed the conjecture proposed by Dubinsky et al. that if a graph has a star spanning tree, i.e., a spanning tree in which one point is adjacent to all other points, then this star spanning tree has the minimum number of tree intersections.<\/p>\n","protected":false},"excerpt":{"rendered":"
\u7814\u7a76\u4e3b\u984c\uff1a\u6700\u5c0f\u751f\u6210\u6a39\u74b0\u4ea4\u96c6\u5047\u8a2d\u8b49\u660e \u64b0\u5beb\uff1a\u5b78\u751f\u738b\u99a8 \u5728\u6700\u5c0f\u751f\u6210\u6a39\u74b0\u4ea4\u96c6 (Minimum Spa […]\n","protected":false},"author":2,"featured_media":1890,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[19],"tags":[],"class_list":["post-1889","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-award"],"jetpack_featured_media_url":"https:\/\/www.bebi.ntu.edu.tw\/wp-content\/uploads\/2022\/08\/figure.png","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.bebi.ntu.edu.tw\/index.php?rest_route=\/wp\/v2\/posts\/1889","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.bebi.ntu.edu.tw\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.bebi.ntu.edu.tw\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.bebi.ntu.edu.tw\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.bebi.ntu.edu.tw\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1889"}],"version-history":[{"count":1,"href":"https:\/\/www.bebi.ntu.edu.tw\/index.php?rest_route=\/wp\/v2\/posts\/1889\/revisions"}],"predecessor-version":[{"id":1891,"href":"https:\/\/www.bebi.ntu.edu.tw\/index.php?rest_route=\/wp\/v2\/posts\/1889\/revisions\/1891"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.bebi.ntu.edu.tw\/index.php?rest_route=\/wp\/v2\/media\/1890"}],"wp:attachment":[{"href":"https:\/\/www.bebi.ntu.edu.tw\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1889"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.bebi.ntu.edu.tw\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1889"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.bebi.ntu.edu.tw\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1889"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}