그래프는 데이터를 그림으로 나타낸 것을 뜻하기도 하고, 점(vertex)이 선(edge)으로 연결된 것을 뜻하기도 함.
edge PAGENAME TBD: 선 간선 에지 ....
node PAGENAME TBD: 점 정점 노드 ....
그래프는
집합,set에서의
이진관계,binary_relation(chk: Is this vertex간의 연결,connection(syn. adjacency?) 관계(관계,relation 관계,relationship)?)를 표현하는 수학적 구조.
주로 유한집합
를 생각해 그 원소들을 꼭짓점vertex이라고 부르고,
라는
의 원소들의 (순서가 없는) 쌍으로 이루어진 집합으로 생각해, 그 원소들을 변edge이라고 부르며, 그래프는 꼭짓점 집합과 변 집합의 순서쌍
로 표현.
그래프
에서
- 두 꼭짓점 사이에 변이 있으면,
- 즉 가 성립하면,
두 꼭짓점
가 연결되어 있거나 인접하였다고 함. // connected, adjacent
개의 꼭짓점에서 모든 꼭짓점의 쌍이 서로 인접한 그래프를
개의 꼭짓점을 가진
완전그래프,complete_graph라고 부르고,
으로 표시.
Sub:
클릭,clique
완전그래프,complete_graph
완벽그래프,perfect_graph
평면그래프,planar_graph 평면성그래프?
단순그래프,simple_graph
부분그래프,subgraph 부분그래프 서브그래프 ....중에?
directed_graph 유향그래프 (
有向グラフ ) 방향성그래프 ... 방향그래프?
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
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
수학백과: 이분그래프 참조
sparse_graph
dense_graph
(대충) 이건 특정한 그래프는 아니고 연결된 정도의
밀도,density에 따른 분류인데 둘을 나누는 명확한 기준은 없으며, node의 수와 edge의 수를 비교하여 상대적으로 정해지는? CHK
graph_complement or complement_graph or complementary_graph - writing
////그래프관련주제////
{
두 그래프 G, H의
강한 곱, 강한곱, 강곱?
기호: G⊠H
2. 구성: optional한 요소 ¶
weight -
가중값,weight, 있으면 weighted_graph
edge의 성질.
ex. vertex 간을 이동하는 시간, 이동하는 비용...
방향성 directionality - 있는지 여부에 따라 나뉨. directed_graph vs undirected_graph
edge의 성질.
차수 degree - degree of a vertex
유향그래프의 경우
인접 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
트레일 trail : edge가 중복되지 않는 walk
경로,path : node가 중복되지 않는 trail
닫힌 보행 closed walk : 시작node와 끝node가 같은 walk
닫힌 트레일 closed trail - 일부 저자들은 이걸
회로,circuit 또는
여행,tour이라고도 한다
순환,cycle : closed path 닫힌 경로 -
닫힌경로,closed_path
path의 출발과 도착이 같은 경우.
그래프 전체를 거치는 walk
Eulerian_trail : 모든 edge가 정확히 한 번씩 포함된 closed trail. (node가 중복될 수 있어, path는 아니라고..)
wpko '오일러 경로'는
한붓그리기로 redirected.
해밀턴_경로,Hamiltonian_path : 모든 node를 정확히 한 번씩 거치는 path.
부분그래프 subgraph 서브그래프
//
위상,topology수학적 성질은..
연결그래프 connected graph
연결_그래프 : 모든 두 node 사이에 path가 존재하는 graph.
비연결그래프 disconnected graph
연결성분 connected component
오일러 지표 Euler characteristic =
오일러_지표 - homology? -
종수,genus 언급. genus가 0인 그래프는
평면그래프,planar_graph.
오일러 지표 Euler characteristic - homology? -
종수,genus 언급. genus가 0인 그래프는
평면그래프,planar_graph.
....
불변량,invariant
see also twin:
수학백과: 그래프 이론 주요 용어(https://terms.naver.com/entry.naver?docId=3404983&cid=47324&categoryId=47324)
4. 분류 TODO 위쪽 Sub: 로 옮길 것 ¶
단순그래프 simple graph
{ chk
두 node를 연결하는 ..(edge?)..가 최대 하나. 둘 이상이면 x. 또는 한 node에서 자기 자신으로 가는
루프,loop가 있어도 x.
고리나 다중변을 갖지 않는 그래프.[*
}
여러 그래프
// 처음배우는인공지능 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 : 유향 그래프 변이나 정점에 가중치 정보가 추가된 그래프
가중_그래프
간선 가중 그래프 edge-weighted_graph : 변에 가중치를 나타낸 그래프
정점 가중 그래프 vertex-weighted_graph : 정점에 가중치를 나타낸 그래프
네트워크,network : = 가중 그래프
ADDHERE
Sub:
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을 빼준 것.
9. 그래프의 일반화 ¶
그래프는 edge가 정확히 2개의 vertex만 만날(join) 수 있는데,
하이퍼그래프,hypergraph는 개수 제한이 없다. (WpEn) (보면 여러 정점들을 거치는 것을 볼 수 있음.)
10. 학습 도움 사이트 - 시각화visualization .... ¶
성냥개비 그래프(matchstick graph) - 취미 수학 영역?
평면에 펼쳐 놓은, 두 점을 연결하는 선이 모두 길이가 같은 선분인 그래프
365일 수학: 3-정규 성냥개비 그래프(https://terms.naver.com/entry.naver?docId=5145696&cid=60205&categoryId=60205)
13. TBD: 그래프와 네트워크의 관계 ¶
위에 여러 sources를 통해 써놓은 거 보면 그래프 중
- 유향그래프가 네트워크라는 곳도 있고
- 유향 가중그래프가 네트워크라는 곳도 있고
- (그 외에) 동의어로 서술한 곳도 있다.
아무튼
그래프,graph 네트워크,network 둘은 유의어이며 sources에 따라 정의가 다르다.
둘을 완전히 구분하는 것은 불가능.
graph가 좀더 뜻이 일반적인 듯.
어떤 내용을 graph에, 어떤 내용을 network에 주로 적을지 TBD.
15. Etc 1 (보통, 이산수학/조합론/CS/graph_theory 제외한 수학에서 일컫는 그래프) 함수의 그래프 + 음함수의 그래프 ¶
보통 그리는 법(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의 그래프.
함수
정의역이
이면 그
그래프는 데카르트 평면 위의 점들로 구성. 좌표들은
의 입출력 쌍들. 집합 표기법을 쓰면
그래프는:
(Thomas Calc.)
(Thomas)
}
즉 2D에서 그래프는 곡선, 3D에서 그래프는 곡면, nD에서 그래프는 (...) ...? chk
표현
graphing n. 그래프 그리기
Twins:
수학백과: 함수의 그래프(https://terms.naver.com/entry.naver?docId=3338317&cid=47324&categoryId=47324)
16. Etc 2 (통계자료의 시각화 등에 쓰이는 그래프) ¶
bar graph, pie graph, 이런것들
위에 Etc 1 과 완전히 구분되는건 아닌듯??
17. Etc 3 (logic - 이것도 논리학에서 시각화를 위한?) logical graph ¶
logical_graph
logical graph
번역? 논리그래프 - 가 최선?
18. Etc 4 - knowledge graph ¶
knowledge_graph
knowledge graph
번역? 지식그래프 - 가 최선?
19. Etc 5 - graph database ¶
graph_database
graph database