Re: [閒聊] Biconnected Components

看板Marginalman作者dinghaipi (果凍魚)時間9年前 (2017/01/09 02:28)推噓4(4推 0噓 8→)

留言12則, 5人參與討論串10/10 (看更多)

※ 引述《deepLearning (深度學習)》之銘言： : ※ 引述《ILoveElsa (廢文十傑九席香草醬油)》之銘言： : : In graph theory, a biconnected component (also known as a block or : : 2-connected component) is a maximal biconnected subgraph. Any connected graph : : decomposes into a tree of biconnected components called the block-cut tree of : : the graph. The blocks are attached to each other at shared vertices called : : cut vertices or articulation points. Specifically, a cut vertex is any vertex : : whose removal increases the number of connected components. : 看到這個就讓我想到當初第一章竟然要我證明這個 : Let G be a graph. A clique in G is a subgraph in which every : two nodes are connected by an edge. An anti-clique, also called an independent : set, is a subgraph in which every two nodes are not connected by an edge. Show : that every graph with n nodes contains either a clique or an anti-clique with : at least : 1 : (--- log n ) nodes. : 2 2 : 我想好久豆頁女子痛 Make space for two piles of nodes , A and B . Then , starting with the entire graph , repeatedly add each remaining node x to A if its degree is greater than one half the number of remaining nodes and to B otherwise , and discard all nodes to which x isn't(is) connected if it was added to A(B) . Continue until no nodes are left. At most half of the nodes are discarded at each of these steps , so at least log2 n steps will occur before the process terminates . Each step adds a node to one of the piles , so one of the piles ends up with at least 1/2log2 n nodes. The pile contains the nodes of a clique and the B pile contains the nodes of an anti-clique. 少年我只能幫你們到這了 ----- Sent from JPTT on my Sony E6853. -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.246.73 ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1483900137.A.44A.html

推

js0071724

01/09 02:29, , 1^F

01/09 02:29, 1^F

→

dinghaipi

01/09 02:30, , 2^F

01/09 02:30, 2^F

→

js0071724

01/09 02:31, , 3^F

01/09 02:31, 3^F