что означает крупнейший_ cc в графе

Question

Я пытаюсь создать граф, где я встретил термин, называемый самым большим подключенным компонентом

, поэтому я хочу понять, что на самом деле подразумевается под ним.

Предположим, у меня есть граф G и если применить нижеприведенный фрагмент кода, получим узлы

largest_cc = max(nx.connected_components(G), key=len)

Предположим, что в графе g есть 10 узлов (a1, a2, a3, a4, a5, a6, a7, a8, a9, a10)

и есть грань между ((a1, a2), (a3, a6), (a1, a4), (a1, a8), (a1, a9), (a5, a10), (a7, a8 ), (a8, a10))

поэтому самый большой связанный компонент даст мне узлы a1, a2, a4, a8, так как a1 имеет максимальное количество имеющихся ребер ??

мое понимание верно ? или есть что-то еще

Answer 1

Связанный компонент в неориентированном графе - это набор узлов, которые можно получить из любого узла компонента в любой другой, следуя ребрам. Самый большой компонент - это компонент с наибольшим количеством узлов.

Представьте, что каждое ребро является строкой. Вы берете один узел и вытаскиваете его из кучи, и продолжаете вытягивать узлы, пока не останется больше кусков нити, соединяющих узлы, которые вы вытащили, с оставшейся кучей узлов. То, что вы вытащили, это подключенный компонент исходного узла, который вы захватили.

Так что нет, в вашем примере a3 и a6 не составят подключенный компонент (у них нет других ребер ), но остальные узлы также составляют связанный компонент (так как вы можете добраться от любого из них до любого другого). Этот компонент других узлов является самым крупным.