<jupyter_start><jupyter_text>그래프 이론 기초 1. 기초- node=vertex - edge$$G_{graph} = (V_{set}, E_{edge}) $$ 2. Walk, Trail, Path, Cycle- walk: 출발지에서 목적지까지 노드의 순서열- trail: 동일 노드 두 번 이상 지나지 않음- path: 시작 & 끝만 두 번 이상 가능- cycle: 시작 & 끝 동일- code    - `has_path`    - `shortest_path` 3. Clique- 무방향성 그래프 & 모든 노드끼리 간선 존재 -> 노드 집합은 **클리크**- 최대 클리크: 다른 인접 노드 추가시 클리크 아니게 되는 것- code    - `enumerate_all_cliques`    - `find_cliques`: 모든 최대 클리크<jupyter_code># 클리크: abc 
# 최대클리크: abc, bcd
g = nx.Graph()
g.add_node("a")
g.add_node("b")
g.add_node("c")
g.add_node("d")

g.add_edge("a", "b")
g.add_edge("a", "c")
g.add_edge("d", "b")
g.add_edge("b", "c")
g.add_edge("d", "c")

d = to_pydot(g)
d.set_dpi(100)
d.set_rankdir("LR")
Image(d.create_png())
# a 노드 포함하는 클리크 찾기
nx.cliques_containing_node(g, ['a'])
nx.cliques_containing_node(g, ['a', 'b'])
# 모든 클리크 찾기
[c for c in nx.enumerate_all_cliques(g)]
# 최대 클리크 찾기
[c for c in nx.find_cliques(g)]<jupyter_output><empty_output><jupyter_text>NetworkX 패키지<jupyter_code>import networkx as nx
from IPython.core.display import Image
from networkx.drawing.nx_pydot import to_pydot
g = nx.DiGraph()
g.add_node('a')
g.add_node('b')
g.add_node('c')
g.add_node('d')
g.add_node('e')

g.add_edge('a','c')
g.add_edge('b','c')
g.add_edge('d','e')
g.add_edge('c','e')

d = to_pydot(g)
Image(d.create_png())<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.19776951672862453, 'fraction_numerical': 0.0044609665427509295, 'mean_word_length': 4.801724137931035, 'pattern_counts': {'":': 0, '<': 9, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '372775', 'license': 'MIT', 'n_tokens_mistral': 758, 'n_tokens_neox': 879, 'n_words': 146, 'path': '06.Math/19.1 graph basic.ipynb', 'repo_name': 'HenryPaik1/Study', 'size': '1345'}