#noindex
그래프는 데이터를 그림으로 나타낸 것을 뜻하기도 하고, 점(vertex)이 선(edge)으로 연결된 것을 뜻하기도 함.

''edge PAGENAME TBD: 선 간선 에지  ....''
''node PAGENAME TBD: 점 정점 노드 ....''

그래프 G는 집합의 순서쌍 (V, E)로서
V의 원소는 [[정점,vertex]], 꼭지점, [[노드,node]]라 하고
E의 원소는 변, [[간선,edge]]이라 하며 
V×V의 원소를 그 원소로 하는 [[다원집합,multiset]]이다.

그래프는 [[집합,set]]에서의 [[이진관계,binary_relation]]''(chk: Is this vertex간의 [[연결,connection]](syn. [[Srch:adjacency]]?) 관계([[관계,relation]] [[관계,relationship]])?)''를 표현하는 수학적 구조.
주로 유한집합 $V$ 를 생각해 그 원소들을 꼭짓점vertex이라고 부르고,
$E=\lbrace\lbrace u,v \rbrace : u,v \in V \rbrace$ 라는 $V$ 의 원소들의 (순서가 없는) 쌍으로 이루어진 집합으로 생각해, 그 원소들을 변edge이라고 부르며, 그래프는 꼭짓점 집합과 변 집합의 순서쌍 $(V,E)$ 로 표현.
그래프 $G=(V,E)$ 에서
 * 두 꼭짓점 $u,v$ 사이에 변이 있으면,
 * 즉 $\lbrace u,v \rbrace \in E$ 가 성립하면,
두 꼭짓점 $u,v$ 가 연결되어 있거나 인접하였다고 함. // connected, adjacent
$n$ 개의 꼭짓점에서 모든 꼭짓점의 쌍이 서로 인접한 그래프를 $n$ 개의 꼭짓점을 가진 [[완전그래프,complete_graph]]라고 부르고, $K_n$ 으로 표시.[* https://horizon.kias.re.kr/17100/ "자연수 집합 이외에도"]

----
Sub:
 [[클릭,clique]]
 [[완전그래프,complete_graph]]
 [[완벽그래프,perfect_graph]]
 [[평면그래프,planar_graph]] 평면성그래프?
 [[단순그래프,simple_graph]]
  고리나 평행변을 갖지 않는 그래프.
   고리와 평행변은 (수학백과: 그래프) 참조
  고리나 다중변을 갖지 않는 그래프.[* https://terms.naver.com/entry.naver?docId=3338375&cid=47324&categoryId=47324 비징의 정리]
  [[simple_directed_graph]]
  https://proofwiki.org/wiki/Definition:Simple_Graph
 [[부분그래프,subgraph]] 부분그래프 서브그래프 ....중에?
  [[spanning_subgraph]] - writing
   모든 vertex를 포함한 [[부분그래프,subgraph]] (wpko)
   (대충) 원래 그래프와 노드는 같고, 일부 edge만 포함된. ... 그리고 모두 연결되어야? chk
   mklink [[spanning_tree]]
   WpKo:신장_부분_그래프
   https://proofwiki.org/wiki/Definition:Spanning_Subgraph 를 포면 graph의 [[factor]]라고도 한다는데. 저걸 번역한다면? 요소? 인자? chk
   ... Google:spanning+subgraph
  [[유도된부분그래프,induced_subgraph]]
  이 셋은 see [[https://terms.naver.com/entry.naver?docId=3404981&cid=47324&categoryId=47324]]
  https://proofwiki.org/wiki/Definition:Subgraph
 directed_graph 유향그래프 (WtEn:有向グラフ ) 방향성그래프 ... 방향그래프?
  '''directed graph'''
  edge가 [[방향성,directionality]]을 가지는 graph.
  Sub: [[simple_directed_graph]] [[DAG,directd_acyclic_graph]]
  WtEn:directed_graph 
  https://mathworld.wolfram.com/DirectedGraph.html
  https://ncatlab.org/nlab/show/directed+graph 그리고 별도 페이지에 있는
  https://ncatlab.org/nlab/show/digraph
  https://encyclopediaofmath.org/wiki/Graph,_oriented
  https://proofwiki.org/wiki/Definition:Directed_Graph
  https://xlinux.nist.gov/dads/HTML/directedGraph.html
  mklink [[quiver]]
 undirected_graph
  edge가 [[방향성,directionality]]을 가지지 않고 [[연결,connection]]만을 하는 그래프.
  '''undirected graph'''
  번역tbd, 무향그래프 (WtEn:無向グラフ ) 비방향성그래프 ....?
  WtEn:undirected_graph
  https://xlinux.nist.gov/dads/HTML/undirectedGraph.html
  https://mathworld.wolfram.com/UndirectedGraph.html
  "undirected graph" Ggl:"undirected graph"
 [[quiver]] (writing)

 simple_graph https://mathworld.wolfram.com/SimpleGraph.html
 weighted_graph
  https://mathworld.wolfram.com/WeightedGraph.html - [[가중값,weight]]이 branch에? branch 가 뭐지? edge 말하는거? - Yes.[* https://mathworld.wolfram.com/GraphEdge.html]
  https://xlinux.nist.gov/dads/HTML/weightedGraph.html ''(edge-weighted graph)''
  weighted and directed graph
   https://xlinux.nist.gov/dads/HTML/weightedDigraph.html
 regular_graph
  https://mathworld.wolfram.com/RegularGraph.html
  https://freshrimpsushi.github.io/posts/regular-graph/
 [[순환그래프,cycle_graph]] = circuit_graph - goto [[순환,cycle#s-4]]
  vertex 개수 ≥ 3인 경우
  https://mathworld.wolfram.com/CycleGraph.html
  [[WpEn:Cycle_graph]]
 cyclic_graph
  [[순환,cycle]]
  compare cycle_graph
  https://mathworld.wolfram.com/CyclicGraph.html
 acyclic_graph
  [[순환,cycle]] 없는?
  Sub:
  [[DAG,directed_acyclic_graph]]
  https://mathworld.wolfram.com/AcyclicGraph.html - graph_cycle([[순환,cycle]])이 없는. 이건 bipartite_graph 임.
 unicyclic_graph
  [[순환,cycle]] 하나?
  https://mathworld.wolfram.com/UnicyclicGraph.html
 cube_graph
  Google:cube+graph
  
 [[트리,tree]]
 pseudotree https://mathworld.wolfram.com/Pseudotree.html

 [[이분그래프,bipartite_graph]]
{
//from mathworld
[[k분그래프,k-partite_graph]]에서 k=2인 경우.
모든 acyclic_graph는 bipartite.

//from it용어사전
무방향그래프임.

sub: [[완전이분그래프,complete_bipartite_graph]]

Twins:
[[https://terms.naver.com/entry.naver?docId=855702&cid=50371&categoryId=50371 IT용어사전: 이분 그래프]]
[[https://terms.naver.com/entry.naver?docId=3405266&cid=47324&categoryId=47324 수학백과: 이분그래프]]
https://mathworld.wolfram.com/BipartiteGraph.html
[[WpKo:이분_그래프]]
[[WpEn:Bipartite_graph]] - aka '''bigraph'''
[[https://encyclopediaofmath.org/wiki/Graph,_bipartite]]

Up: [[그래프,graph]] > k-partite_graph
 [[분할,partition]] > [[이분,bipartition]]
}
 [[완전이분그래프,complete_bipartite_graph]]
{
그 중에서도 특별한 경우가 별(star) [[별,star]]
수학백과: 이분그래프 참조

[[WpEn:Complete_bipartite_graph]] - aka '''biclique'''
[[WpKo:완전_이분_그래프]] - 정의에 [[집합의_분할,set_partition]] 언급됨.
https://mathworld.wolfram.com/CompleteBipartiteGraph.html

See also:
https://mathworld.wolfram.com/CompleteTripartiteGraph.html 완전삼분그래프
https://mathworld.wolfram.com/Completek-PartiteGraph.html 완전k분그래프
 ( 이것은 https://mathworld.wolfram.com/k-PartiteGraph.html k분그래프 의 일종 )

Up: [[완전그래프,complete_graph]] [[이분그래프,bipartite_graph]]
}

 k-partite_graph https://mathworld.wolfram.com/k-PartiteGraph.html

 connected_graph https://mathworld.wolfram.com/ConnectedGraph.html
 disconnected_graph https://mathworld.wolfram.com/DisconnectedGraph.html

 empty_graph
  node가 n개, edge가 0개. https://mathworld.wolfram.com/EmptyGraph.html
 null_graph
  empty_graph를 뜻하기도 하고, node가 0개, edge가 0개인 그래프를 뜻하기도 함. https://mathworld.wolfram.com/NullGraph.html
  [[WpEn:Null_graph]] - may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
   [[WpKo:무변_그래프]] - "무변 그래프(無邊graph, 영어: edgeless graph)는 꼭짓점을 가질 수 있지만, 변을 가지지 않는 그래프이다."
  https://proofwiki.org/wiki/Definition:Null_Graph
 edgeless_graph
  edge가 0개. (즉 이건 덜 모호한 용어.)
  https://proofwiki.org/wiki/Definition:Edgeless_Graph
 singleton_graph
  node가 한 개, edge가 0 개. https://mathworld.wolfram.com/SingletonGraph.html

 labeled_graph
  See also weighted_graph
  https://mathworld.wolfram.com/LabeledGraph.html
  https://xlinux.nist.gov/dads/HTML/labeledgraph.html

 Eulerian_graph Euler_graph
  [[오일러_순환,Eulerian_cycle]]을 포함한 [[그래프,graph]].
  https://mathworld.wolfram.com/EulerianGraph.html

 [[해밍_그래프,Hamming_graph]] w
  MathWorld:HammingGraph
  WpEn:Hamming_graph

path_graph = linear_graph
[[WpEn:Path_graph]]
[[WpKo:경로_그래프]] "는 모든 꼭짓점의 차수가 2 이하인 나무"
mklink: [[경로,path]]와? < Up: [[경로,path]] [[그래프,graph]] 인가? >
https://mathworld.wolfram.com/PathGraph.html
(주의 linear_graph 말고 line_graph 는 별도)

sparse_graph
dense_graph
(대충) 이건 특정한 그래프는 아니고 연결된 정도의 [[밀도,density]]에 따른 분류인데 둘을 나누는 명확한 기준은 없으며, node의 수와 edge의 수를 비교하여 상대적으로 정해지는? CHK

graph_complement or complement_graph or complementary_graph - writing

////그래프관련주제////
 [[그래프색칠,graph_coloring]] - notes.txt에 작성중
 [[그래프순회,graph_traversal]] - 현재 notes.txt =순회,traversal 에 작성중
 그래프동형 graph_isomorphism ?? [[https://terms.naver.com/entry.naver?docId=3404984&cid=47324&categoryId=47324 수학백과: 그래프 동형]]
 [[독립집합,independent_set]] - curr goto [[독립성,independence#s-8]]
 [[강한곱,strong_product]]
{
두 그래프 G, H의 '''강한 곱, 강한곱, 강곱?'''

기호: G⊠H

⊠ <- 이건 유니코드의 [[https://en.wiktionary.org/wiki/%E2%8A%A0]] [[https://unicode-table.com/kr/22A0/]] 근데 폰트에 따라 ballot box? 처럼, X가 네모 안에 딱 맞지 않게 나오는 경우가 있다. 표현에는 TeX의 \boxtimes 가 적합한데 mimeTeX가 지원을 안한다.
codecogs에서 가져오면,
http://latex.codecogs.com/gif.latex?%5Cboxtimes?.gif

See https://horizon.kias.re.kr/17100/ 중간쯤 ('램지 이론 활용의 예' 문단) "이때 두 그래프"
{
[[그래프,graph]]의 [[강한곱,strong_product]]의 [[독립수,independence_number]]를 [[램지_수,Ramsey_number]]를 써서 계산 가능.

Related: [[독립수,independence_number]], [[독립집합,independent_set]], [[램지_이론,Ramsey_theory]]? / [[램지_정리,Ramsey_theorem]]? / [[램지_수,Ramsey_number]]
}

Twins:
https://mathworld.wolfram.com/GraphStrongProduct.html
[[WpEn:Strong_product_of_graphs]] - aka '''normal_product, AND_product'''
[[Google:strong.product]]

Up: [[이항연산,binary_operation]]? [[그래프곱,graph_product]]
}
 [[그래프곱,graph_product]]
{
Sub:
 graph_Cartesian_product
  WpKo:그래프_데카르트_곱
  https://mathworld.wolfram.com/GraphCartesianProduct.html
 categorical product
 graph lexicographic product
 graph strong product
  see [[강한곱,strong_product]]

Twins:
[[https://mathworld.wolfram.com/GraphProduct.html]]
[[https://www2.ccs.neu.edu/research/demeter/design-decisions/traversal-strategies/products/Graph%20Product%20--%20from%20MathWorld.htm]]
WpEn:Graph_product
}

graph_likelihood /// [[가능도,likelihood]]에 있었는데 가능도가 아니라 닮음정도 닮음도 같은 거 같아서 여기로 가져옴
{
https://mathworld.wolfram.com/GraphLikelihood.html
[[그래프,graph]] [[단순그래프,simple_graph]]
}


<<tableofcontents>>

= 구성: 필수적인 요소 =
가장 기본적인 두가지부터 어휘 및 그 번역어가 너무 다양. (주의. 이 학문은 수많은 graph 종류의 정의부터도 책에 따라 조금씩 다른 경우가 많음. TODO 예시 추가)
||V||vertex 버텍스 node 노드 ||정점 꼭짓점 마디 교점 ||[[점,point]]에 비유 ||object에 비유?? ||
||E||edge 에지 엣지 link 링크 arc 아크 ||변 간선 모서리 ||선line에 비유 ||([[경로,path]] 거치는 거 말고 직접 바로) 연결, link, connection, [[관계,relationship]]에 비유 ||

대충 같이 쓰이는 쌍을 좀 분류하면
||node||vertex||정점 ||점 ||
||link||edge  ||변   ||선 ||

graph_vertex
https://mathworld.wolfram.com/GraphVertex.html
graph_edge
https://mathworld.wolfram.com/GraphEdge.html

vertex_set
https://proofwiki.org/wiki/Definition:Vertex_Set
edge_set
https://proofwiki.org/wiki/Definition:Edge_Set
// [[집합,set]]

= 구성: optional한 요소 =
weight - [[가중값,weight]], 있으면 weighted_graph
 edge의 성질.
 ex. vertex 간을 이동하는 시간, 이동하는 비용...
방향성 directionality - 있는지 여부에 따라 나뉨. directed_graph vs undirected_graph
 edge의 성질.

= 용어 =
차수 degree - degree of a vertex
 node의 성질.
 한 node에 연결된 edge의 수.
 한 vertex에 연결된 edge의 개수.
 directed_graph/undirected_graph에 따라 용어가 달라짐.
  undirected일 때는 그냥 degree.
  directed일 때는 indegree / outdegree.
 꼭짓점의 차수(degree of a vertex)는 해당 꼭짓점과 결합하고 있는 변의 개수를 뜻한다.[* 수학백과: 그래프]
 [[https://terms.naver.com/entry.naver?docId=5668996&cid=60207&categoryId=60207 수학백과: 꼭짓점의 차수]]
 https://freshrimpsushi.github.io/posts/degree-in-graph-theory/

유향그래프의 경우
 입력차수 in-degree : node로 들어오는 edge의 수 // https://xlinux.nist.gov/dads/HTML/indegree.html
 출력차수 out-degree : node에서 나가는 edge의 수 // https://xlinux.nist.gov/dads/HTML/outdegree.html

인접 adjacency (adj. adjacent) : 두 node 사이에 edge가 존재하면 이것들은 인접.
 즉 두 node(vertex)의 성질.

adjacent - 직접연결된
connected - 직간접적으로 연결된 .... ??? CHK

incident/adjacent, incidence/adjacency
 두 node가 한 edge로 연결되어 있을 경우,
  이 두 nodes는 adjacent(인접).
  그리고 이 edge는 두 nodes에 incident(부속). (김황남, via ratsgo)

고리와 링크 - 변의 두 분류
고리(loop) : 양 끝점이 같은 변
링크(link) : 양 끝점이 서로 다른 변
see 그림 2 at 수학백과 '고리와 링크'

평행변(parallel edges) 또는 다중변(multiple edges) : 끝점들의 짝이 같은 두 개 이상의 링크들
see 수학백과 '평행변'

보행 walk https://mathworld.wolfram.com/Walk.html
 해밀턴_보행? Hamiltonian_walk https://mathworld.wolfram.com/HamiltonianWalk.html
트레일 trail : edge가 중복되지 않는 walk
[[경로,path]] : node가 중복되지 않는 trail
 https://mathworld.wolfram.com/Path.html
 https://mathworld.wolfram.com/GraphPath.html
 ([[path_graph]]는 다른 것임)
 [[WpKo:경로_(그래프_이론)]]
  같은 node를 거듭해서 거치지 않는 edge들의 sequence.
  유향그래프에서는 유향경로(=방향경로=dipath)가 있음.
  단순경로 : 처음node와 끝node를 제외하고 중복된 정점이 없는 경로(???)
 [[WpEn:Path_(graph_theory)]]
닫힌 보행 closed walk : 시작node와 끝node가 같은 walk
닫힌 트레일 closed trail - 일부 저자들은 이걸 [[회로,circuit]] 또는 [[여행,tour]]이라고도 한다
[[순환,cycle]] : closed path 닫힌 경로 - [[닫힌경로,closed_path]]
 path의 출발과 도착이 같은 경우.[* https://m.blog.naver.com/minichuuuuu/220808115381]

그래프 전체를 거치는 walk
 Eulerian_trail : 모든 edge가 정확히 한 번씩 포함된 closed trail. (node가 중복될 수 있어, path는 아니라고..)
  wpko '오일러 경로'는 [[WpKo:한붓그리기]]로 redirected.
 해밀턴_경로,Hamiltonian_path : 모든 node를 정확히 한 번씩 거치는 path.
  비교: [[오일러_경로,Eulerian_path]] - Srch:Eulerian_path or Srch:Euler_path
  [[WpKo:해밀턴_경로]]
  WpSimple:Hamiltonian_path
  WpEn:Hamiltonian_path
  [[경로,path]]
  Hamiltonian_cycle 해밀턴_순환 ? : 시작node와 끝node가 같은 Hamiltonian_path.
   [[순환,cycle]]

부분그래프 subgraph 서브그래프
 [[클릭,clique]]
 [[생성나무,spanning_tree]] = 신장 부분 그래프 spanning subgraph - [[WpKo:신장_부분_그래프]]
 유도부분그래프 induced subgraph
 [[WpKo:그래프_마이너]] - edge를 contraction시켜 얻는 graph. // edge_contraction
 이걸 일반화시키면 [[matroid_minor]] - see [[매트로이드,matroid]].
  Up: [[마이너,minor]]

// [[위상,topology]]수학적 성질은..
연결그래프 connected graph
 [[WpKo:연결_그래프]] : 모든 두 node 사이에 path가 존재하는 graph.
비연결그래프 disconnected graph
연결성분 connected component
오일러 지표 Euler characteristic = $\chi=v-e+f.$ [[WpKo:오일러_지표]] - homology? - [[종수,genus]] 언급. genus가 0인 그래프는 [[평면그래프,planar_graph]].
오일러 지표 Euler characteristic - homology? - [[종수,genus]] 언급. genus가 0인 그래프는 [[평면그래프,planar_graph]].
....[[불변량,invariant]]

[[평면그래프,planar_graph]]

// 크기 척도
두 node 사이의 [[거리,distance]]
 경로가 없으면 길이 [[무한대,infinity]]
[[이심률,eccentricity]]
[[지름,diameter]] : 최대 이심률
''//이상 geometry 용어 재활용함을 볼 수 있음.''
가중그래프 weighted graph - edge에 [[가중값,weight]]이 주어진 그래프.
 [[WpKo:가중_그래프]] : 가중 그래프 중 [[유향그래프]]를 [[네트워크,network]]라고 한다고.

// 이상 주로 용어 [[WpKo:그래프_이론_용어]] 참고하여 기본적 골격, chk 

see also twin:
[[https://terms.naver.com/entry.naver?docId=3404983&cid=47324&categoryId=47324 수학백과: 그래프 이론 주요 용어]]

= 분류 ''TODO 위쪽 Sub: 로 옮길 것'' =
단순그래프 simple graph
{ chk
두 node를 연결하는 ..(edge?)..가 최대 하나. 둘 이상이면 x. 또는 한 node에서 자기 자신으로 가는 [[루프,loop]]가 있어도 x.

고리나 다중변을 갖지 않는 그래프.[* 
}

멀티그래프 multigraph - node 사이에 multiple edges. (다중변이 허용되는 경우를 말하기도 하고, 다중변이 있는 경우를 말하기도 함. 따라서 모호성이 있는 용어. [[루프,loop]](graph_loop; vertex에서 같은 vertex로 가는 edge를 뜻함, https://mathworld.wolfram.com/GraphLoop.html )가 없어야 한다고 하기도 하고, 허용하기도 하며, 언급이 없는 등 단어의 모호성 때문에 주의해서 쓰거나 쓰지 말아야 하는 용어.[* MathWorld Multigraph] / [[https://proofwiki.org/wiki/Definition:Loop_(Graph_Theory)]] / [[https://proofwiki.org/wiki/Definition:Loop-Graph]] )
 rel. multiplicity esp graph_multiplicity
 https://mathworld.wolfram.com/Multigraph.html
 https://ncatlab.org/nlab/show/multigraph
 https://proofwiki.org/wiki/Definition:Multigraph

 https://xlinux.nist.gov/dads/HTML/multigraph.html

의사그래프 pseudograph - 자기 자신으로 가는 간선(loop)가 있음
 https://mathworld.wolfram.com/Pseudograph.html
 https://ncatlab.org/nlab/show/pseudograph

유향그래프 방향성그래프 directed_graph = digraph - edge가 방향이 있음
무향그래프
----
여러 그래프
// 처음배우는인공지능 p129
연결그래프 connected_graph : 모든 정점을 연결한 그래프 - [[연결성,connectivity]]
비연결그래프 : 그렇지 않은 그래프
고립 정점 isolated_vertex : 어떤 다른 정점도 연결되지 않은 정점
평행 변 parallel_edge : 정점 2개가 2개 이상의 변으로 연결된 변
양 끝이 같은 변 self-loop : 1개의 정점에 시작과 끝이 연결된 변 // https://xlinux.nist.gov/dads/HTML/selfloop.html
유향 그래프 directed_graph : 변에 방향이 존재하는 그래프
무향 그래프 undirected_graph : 변에 방향이 없는 그래프
유향 비순회 그래프[[directed_acyclic_graph,DAG]] - writing : 어떤 정점에서 출발한 후 해당 정점으로 돌아오는 경로가 하나인 그래프
가중 그래프 weighted_graph : 유향 그래프 변이나 정점에 가중치 정보가 추가된 그래프 WpKo:가중_그래프
간선 가중 그래프 edge-weighted_graph : 변에 가중치를 나타낸 그래프
정점 가중 그래프 vertex-weighted_graph : 정점에 가중치를 나타낸 그래프
[[네트워크,network]] : = 가중 그래프

[[무한그래프,infinite_graph]]
 그럼 opp. [[유한그래프,finite_graph]]?

#linegraph
[#linegraph]
[[선그래프,line_graph]]
https://mathworld.wolfram.com/LineGraph.html
(주의: linear_graph 는 별도의 개념)

#rootgraph
[#rootgraph]
[[루트그래프,root_graph]]?
https://mathworld.wolfram.com/RootGraph.html

ADDHERE

Sub:
== [[클릭,clique]] ==
== [[완전그래프,complete_graph]] ==

= 관련? ''TBW: 어떤관계?'' =
[[트리,tree]] : 출발점이 되는 정점([[루트,root]])가 있는 그래프의 일종
 정확한 정의는 TBW
[[이진_탐색_트리,binary_search_tree]]
[[B-트리,B-tree]]
[[온톨로지,ontology]] - 데이터의 관계를 나타내는 요소를 추가한 트리

= topics =
[[순환,cycle]]
[[경로,path]]
 [[최단경로,shortest_path]] ... kw: pathfinding, path_finding
  [[최단경로문제,shortest_path_problem]] - 최단경로 페이지에서 이걸 분리할 필요가 있나?
  [[WpKo:최단_경로_문제]]
   [[WpKo:플로이드-워셜_알고리즘]] (edge의 weight가 ...) 인 weighted_graph에서 최단경로들을 찾.
   [[WpEn:Floyd–Warshall_algorithm]]
   [[WpKo:데이크스트라_알고리즘]]
   [[WpKo:벨먼-포드_알고리즘]]
   [[WpKo:A*_알고리즘]]

[[순회,traversal]] : algorithm. [[트리,tree]]에도 적용됨.

그래프 곱 graph_product - see [[곱,product]]

↑↓ QQQ 이 둘 관련이? 같은거??

[[WpEn:Cartesian_product_of_graphs]]
QQQ
 cartesian product는 product set([[곱집합,product_set]])이라고도 하는데, 그럼
 cartesian product of graphs도 product set of graphs라고 할 수 있는지?

[[그래프동형,graph_isomorphism]] or 그래프동형사상? 동형그래프 isomorphic_graph ... 관련 [[문제,problem]] - 그래프동형문제
이건 본질적 구조와 연결상태가 중요하고 시각화했을때의 생김새는 전혀 중요하지 않다는거 그건가? or not? ... 그렇다면 [[위상,topology]]적인 주제? CHK 
rel. [[동형사상,isomorphism]]
WpKo:그래프_동형_사상
[[WpEn:Graph_isomorphism]]

= graph theory: 그래프 관련 [[알고리듬,algorithm]] =
//TODO 위 문단과 합칠것.

[[순회,traversal]]
[[깊이우선탐색,depth-first_search,DFS]]
[[너비우선탐색,breadth-first_search,BFS]]
최적 탐색 optimal search
최선 우선 탐색 best-first search
[[에이스타]]? A스타? A* algorithm
 http://www.aistudy.com/heuristic/A_star.htm
미니맥스 원리 mini-max minimax [[WpKo:미니맥스_원리]]
[[알파베타가지치기,alpha-beta_pruning]]

[[최단경로문제,shortest_path_problem]]
[[WpKo:최단_경로_문제]]
[[WpEn:Shortest_path_problem]]

[[WpKo:데이크스트라_알고리즘]] [[WpEn:Dijkstra's_algorithm]]
[[WpKo:벨먼-포드_알고리즘]] [[WpSimple:Bellman-Ford_algorithm]] [[WpEn:Bellman–Ford_algorithm]]

[[그래프색칠,graph_coloring]]
//관련: [[그래프순회,graph_traversal]](curr goto [[순회,traversal]]), [[채색수,chromatic_number]]

= 그래프의 [[자료구조,data_structure]] 표현 =
[[graph_representation]]

그래프를 [[집합,set]], [[행렬,matrix]], [[리스트,list]]로 나타낼 수 있음.

[[표현,representation]] 방법 두가지:
 * [[인접리스트,adjacency_list]] representation // https://xlinux.nist.gov/dads/HTML/adjacencyListRep.html
 * [[인접행렬,adjacency_matrix]] representation // https://xlinux.nist.gov/dads/HTML/adjacencyMatrixRep.html

당연한 그 이유로 인해 - tbw
sparse_graph 에는 adjacency [[리스트,list]]가
dense_graph 에는 adjacency [[행렬,matrix]]이 좋다

----
adjacency_matrix 과 다음 비교
adjacency matrix
degree_matrix
degree matrix
그래프 node가 n개라면 n×n크기의 [[대각행렬,diagonal_matrix]]. 대각성분에 각 node의 degree를 가지고 있고, 대각성분이 아닌 것은 모두 0.
Laplacian_matrix .. [[라플라스_행렬,Laplacian_matrix]]?
Laplacian matrix
degree_matrix에서 adjacency_matrix을 빼준 것.

Naver:"adjacency matrix degree matrix Laplacian matrix"
Ggl:"adjacency matrix degree matrix Laplacian matrix"

== 그래프를 행렬로 나타내는 법 ==
[[인접행렬,adjacency_matrix]] : 정점 사이 관계를 나타내는 행렬. WpKo:인접행렬
[[근접행렬,incidence_matrix]] : 정점과 변의 관계를 나타내는 행렬 WpEn:Incidence_matrix

== list로 ==
인접 리스트(adjacency list)

= 그래프의 일반화 =
[[일반화,generalization]]

그래프는 edge가 정확히 2개의 vertex만 만날(join) 수 있는데, [[하이퍼그래프,hypergraph]]는 개수 제한이 없다. (WpEn) (보면 여러 정점들을 거치는 것을 볼 수 있음.)

https://xlinux.nist.gov/dads/HTML/hypergraph.html
 "A graph whose hyperedges connect two or more vertices."
 hyperedge : https://xlinux.nist.gov/dads/HTML/hyperedge.html
[[WpKo:하이퍼그래프]]
[[WpEn:Hypergraph]]


= 학습 도움 사이트 - 시각화visualization .... =
D3 Graph Theory
https://d3gt.com/
그래프이론공부에 상당히 도움됨. interactive.

= 참고 tmp links ko =
https://ratsgo.github.io/data%20structure&algorithm/2017/11/18/graph/ - 그래프 기본 용어들
[[WpEn:Glossary_of_graph_theory]]

http://www.aistudy.com/math/graph.htm
http://www.aistudy.com/math/graph_theory.htm

= 기타 =
성냥개비 그래프(matchstick graph) - 취미 수학 영역?
평면에 펼쳐 놓은, 두 점을 연결하는 선이 모두 길이가 같은 선분인 그래프
[[https://terms.naver.com/entry.naver?docId=5145696&cid=60205&categoryId=60205 365일 수학: 3-정규 성냥개비 그래프]]

= TBD: 그래프와 네트워크의 관계 =
위에 여러 sources를 통해 써놓은 거 보면 그래프 중
 * 유향그래프가 네트워크라는 곳도 있고
 * 유향 가중그래프가 네트워크라는 곳도 있고
 * (그 외에) 동의어로 서술한 곳도 있다.
아무튼 [[그래프,graph]] [[네트워크,network]] 둘은 유의어이며 sources에 따라 정의가 다르다.
둘을 완전히 구분하는 것은 불가능.
graph가 좀더 뜻이 일반적인 듯.
어떤 내용을 graph에, 어떤 내용을 network에 주로 적을지 TBD.

이 둘의 sub:
 [[그래프이론,graph_theory]]
 [[네트워크이론,network_theory]]
 [[네트워크과학,network_science]]

그리고
그래프의 다른 뜻: 함수 등을 시각화한 것 (이 페이지 아래쪽)
네트워크의 다른 뜻: [[통신,communication]] 등에 쓰이는 [[프로토콜,protocol]] 규칙을 따르는 그거. (sub: [[computer_network]]? [[네트워크프로그래밍,network_programming]] [[네트워크보안,network_security]] etc)

= Twins =
[[https://terms.naver.com/entry.naver?docId=3404981&cid=47324&categoryId=47324 수학백과: 그래프]]
[[https://terms.naver.com/entry.naver?docId=3404982&cid=47324&categoryId=47324 수학백과: 그래프 이론]] (본문은 주로 역사. 끝부분 '같이 읽기'에 여러 주제들 있으니 참조.)
[[https://terms.naver.com/entry.naver?docId=3404983&cid=47324&categoryId=47324 수학백과: 그래프 이론 주요 용어]]
[[WpKo:그래프_이론]]
[[https://terms.naver.com/entry.naver?docId=1068821&cid=40942&categoryId=32204 두산백과: 그래프 이론]]

tmp:
https://everything2.com/title/graph
https://everything2.com/title/graph+theory
수학에서의 그래프와 네트워크 https://freshrimpsushi.github.io/posts/graph-and-network-in-mathematics/

----
= Etc 1 (보통, 이산수학/조합론/CS/graph_theory 제외한 수학에서 일컫는 그래프) 함수의 그래프 + 음함수의 그래프 =

graph of an equation?
graph of a function? [[함수,function]]
집합을 만족하는 좌표 점을 좌표평면에 그린 것??
별도의 페이지로 분리한다면 pagename은? [[함수그래프,function_graph]]?

보통 // [[독립변수와_종속변수]]
가로축에 [[독립변수,independent_variable]]를,
세로축에 [[종속변수,dependent_variable]] 나타냄
수평축/가로축/x축
수직축/세로축/y축

보통 그리는 법(sketching a graph): // 대략적으로
절편(intercept)들을 표시한다.
방정식을 만족하는 점들의 좌표를 구해 평면에 찍고(plot) 점들을 곡선으로 부드럽게 잇는다.

방정식과 부등식의 그래프.
 The '''graph''' of an [[방정식,equation|equation]] or [[부등식,inequality|inequality]] in the variables x and y is the set of all points P(x,y) in the [[평면,plane|plane]] whose coordinates satisfy the equation or inequality.
[[함수,function]]의 그래프.
 함수 $f$ 정의역이 $D$ 이면 그 '''그래프'''는 데카르트 평면 위의 점들로 구성. 좌표들은 $f$ 의 입출력 쌍들. 집합 표기법을 쓰면 '''그래프'''는: $\left{ (x,f(x)) \middle| x\in D \right}$
(Thomas Calc.)

이차원에서
 $\{(x,f(x))|y=f(x)\}$ ......그냥 [[함수,function]]
 $\{(x,y)|f(x,y)=0\}$ ......implicit fn.
그이상차원에서는
 TBW
3차원에서?
{
$f$ 의 [[정의역,domain]] 상의 [[점,point]] $(x,y)$ 에 대한
[[공간,space]]상의 점 $(x,y,f(x,y))$ 의 [[집합,set]]을 $f$ 의 '''그래프'''라고 한다.

$f$ 의 '''그래프'''를 [[곡면,surface]] $z=f(x,y)$ 라고도 부른다.

(Thomas)
}
''즉 2D에서 그래프는 곡선, 3D에서 그래프는 곡면, nD에서 그래프는 (...) ...?  chk''

[[좌표계,coordinate_system]] [[좌표,coordinate]]

표현
graphing n. 그래프 그리기

주제:
[[점근선,asymptote]]
[[플롯,plot]] - 비슷
[[drawing_graph]] or [[graph_drawing]] or [[plotting]]? (아마 [[플롯,plot]] 그리기도 동의어) 이런거
{
[[gnuplot]]
[[맷플럿립,Matplotlib]] - [[파이썬,Python]]으로는 이걸 많이
}

Twins:
[[https://terms.naver.com/entry.naver?docId=3338317&cid=47324&categoryId=47324 수학백과: 함수의 그래프]]

= Etc 2 (통계자료의 시각화 등에 쓰이는 그래프) =
bar graph, pie graph, 이런것들
위에 Etc 1 과 완전히 구분되는건 아닌듯??

관련: [[http://tomoyo.ivyro.net/123/wiki.php/asdf?action=fullsearch&value=scatterplot&context=20&case=1 scatterplot]] [[히스토그램,histogram]] [[시각화,visualization]]
[[차트,chart]]라고도 많이 하는듯?

= Etc 3 (logic - 이것도 논리학에서 시각화를 위한?) logical graph =
logical_graph
logical graph
번역? 논리그래프 - 가 최선?

https://en.wikipedia.org/wiki/Logical_graph

mkl
diagram
[[논리,logic]]
[[논리학,logic]]
[[그래프,graph]]

= Etc 4 - knowledge graph =
knowledge_graph
knowledge graph
번역? 지식그래프 - 가 최선?

mkl
[[지식,knowledge]]
[[자료,data]]
[[위상,topology]]
[[semantic_web]]
[[ontology]]
[[concept_map]] - [[개념,concept]] [[지도,map]]

https://ko.wikipedia.org/wiki/지식_그래프
https://en.wikipedia.org/wiki/Knowledge_graph

= Etc 5 - graph database =
graph_database
graph database

MKL
[[데이터베이스,database]]
[[NoSQL]]
RDF

https://ko.wikipedia.org/wiki/그래프_데이터베이스
https://en.wikipedia.org/wiki/Graph_database

----
Twins:
https://ncatlab.org/nlab/show/graph
[[https://proofwiki.org/wiki/Definition:Graph_(Graph_Theory)]]

Up: [[전산학,compsci]]
분류는 (mathematical_structure and [[자료구조,data_structure]] and abstract_data_type)?