그래프,graph

그래프는 데이터를 그림으로 나타낸 것을 뜻하기도 하고, 점(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$ 으로 표시.[1]


Sub:
클릭,clique
완전그래프,complete_graph
완벽그래프,perfect_graph
평면그래프,planar_graph 평면성그래프?
단순그래프,simple_graph
고리나 평행변을 갖지 않는 그래프.
고리와 평행변은 (수학백과: 그래프) 참조
고리나 다중변을 갖지 않는 그래프.[2]
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]https://terms.naver.com/entry.naver?docId=3404981&cid=47324&categoryId=47324
https://proofwiki.org/wiki/Definition:Subgraph
directed_graph 유향그래프 (WtEn:有向グラフ ) 방향성그래프 ... 방향그래프?
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
regular_graph
순환그래프,cycle_graph = circuit_graph - goto 순환,cycle#s-4
cyclic_graph
acyclic_graph
순환,cycle 없는?
Sub:
DAG,directed_acyclic_graph
https://mathworld.wolfram.com/AcyclicGraph.html - graph_cycle(순환,cycle)이 없는. 이건 bipartite_graph 임.
unicyclic_graph
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용어사전
무방향그래프임.



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



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
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
Eulerian_graph Euler_graph
해밍_그래프,Hamming_graph w
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]수학백과: 그래프 동형
독립집합,independent_set - curr goto 독립성,independence#s-8
강한곱,strong_product
{
두 그래프 G, H의 강한 곱, 강한곱, 강곱?

기호: G⊠H

⊠ <- 이건 유니코드의 [https]https://en.wiktionary.org/wiki/%E2%8A%A0 [https]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를 써서 계산 가능.




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



1. 구성: 필수적인 요소

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

대충 같이 쓰이는 쌍을 좀 분류하면
nodevertex정점
linkedge

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


2. 구성: optional한 요소

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

3. 용어

차수 degree - degree of a vertex
node의 성질.
한 node에 연결된 edge의 수.
한 vertex에 연결된 edge의 개수.
directed_graph/undirected_graph에 따라 용어가 달라짐.
undirected일 때는 그냥 degree.
directed일 때는 indegree / outdegree.
꼭짓점의 차수(degree of a vertex)는 해당 꼭짓점과 결합하고 있는 변의 개수를 뜻한다.[4]
[https]수학백과: 꼭짓점의 차수
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의 출발과 도착이 같은 경우.[5]

그래프 전체를 거치는 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.
부분그래프 subgraph 서브그래프
클릭,clique
생성나무,spanning_tree = 신장 부분 그래프 spanning subgraph - WpKo:신장_부분_그래프
유도부분그래프 induced subgraph
WpKo:그래프_마이너 - edge를 contraction시켜 얻는 graph. // edge_contraction
이걸 일반화시키면 matroid_minor - see 매트로이드,matroid.
// 위상,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


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

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


4. 분류 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 )가 없어야 한다고 하기도 하고, 허용하기도 하며, 언급이 없는 등 단어의 모호성 때문에 주의해서 쓰거나 쓰지 말아야 하는 용어.[6] / [https]https://proofwiki.org/wiki/Definition:Loop_(Graph_Theory) / [https]https://proofwiki.org/wiki/Definition:Loop-Graph )
의사그래프 pseudograph - 자기 자신으로 가는 간선(loop)가 있음
유향그래프 방향성그래프 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 : = 가중 그래프



ADDHERE

Sub:

5. 관련? TBW: 어떤관계?

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

6. topics

순환,cycle
경로,path
최단경로,shortest_path ... kw: pathfinding, path_finding
최단경로문제,shortest_path_problem - 최단경로 페이지에서 이걸 분리할 필요가 있나?
WpKo:최단_경로_문제
순회,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

8. 그래프의 자료구조,data_structure 표현


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

표현,representation 방법 두가지:
당연한 그 이유로 인해 - 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을 빼준 것.


8.1. 그래프를 행렬로 나타내는 법

인접행렬,adjacency_matrix : 정점 사이 관계를 나타내는 행렬. WpKo:인접행렬
근접행렬,incidence_matrix : 정점과 변의 관계를 나타내는 행렬 WpEn:Incidence_matrix

8.2. list로

인접 리스트(adjacency list)

9. 그래프의 일반화


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



10. 학습 도움 사이트 - 시각화visualization ....

D3 Graph Theory
https://d3gt.com/
그래프이론공부에 상당히 도움됨. interactive.

12. 기타

성냥개비 그래프(matchstick graph) - 취미 수학 영역?
평면에 펼쳐 놓은, 두 점을 연결하는 선이 모두 길이가 같은 선분인 그래프
[https]365일 수학: 3-정규 성냥개비 그래프

13. TBD: 그래프와 네트워크의 관계

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

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

15. 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 or inequality in the variables x and y is the set of all points P(x,y) in the 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


표현
graphing n. 그래프 그리기

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


16. Etc 2 (통계자료의 시각화 등에 쓰이는 그래프)

bar graph, pie graph, 이런것들
위에 Etc 1 과 완전히 구분되는건 아닌듯??


17. Etc 3 (logic - 이것도 논리학에서 시각화를 위한?) logical graph

logical_graph
logical graph
번역? 논리그래프 - 가 최선?