Re: [閒聊] Biconnected Components
※ 引述《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
我想好久 豆頁女子痛
--
DO or DO NOT. There is no try.
──Master Yoda
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.100
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1483898078.A.7B7.html
推
01/09 01:58, , 1F
01/09 01:58, 1F
推
01/09 02:00, , 2F
01/09 02:00, 2F
→
01/09 02:08, , 3F
01/09 02:08, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 8 之 10 篇)：