그래프는 데이터를 그림으로 나타낸 것을 뜻하기도 하고, 점(vertex)이 선(edge)으로 연결된 것을 뜻하기도 함.
edge PAGENAME TBD: 선 간선 에지 ....
node PAGENAME TBD: 점 정점 노드 ....
node PAGENAME TBD: 점 정점 노드 ....
그래프 G는 집합의 순서쌍 (V, E)로서
V의 원소는 정점,vertex, 꼭지점, 노드,node라 하고
E의 원소는 변, 간선,edge이라 하며
V×V의 원소를 그 원소로 하는 다원집합,multiset이다.
V의 원소는 정점,vertex, 꼭지점, 노드,node라 하고
E의 원소는 변, 간선,edge이라 하며
V×V의 원소를 그 원소로 하는 다원집합,multiset이다.
그래프는 집합,set에서의 이진관계,binary_relation(chk: Is this vertex간의 연결,connection(syn. adjacency?) 관계(관계,relation 관계,relationship)?)를 표현하는 수학적 구조.
주로 유한집합 를 생각해 그 원소들을 꼭짓점vertex이라고 부르고,
라는 의 원소들의 (순서가 없는) 쌍으로 이루어진 집합으로 생각해, 그 원소들을 변edge이라고 부르며, 그래프는 꼭짓점 집합과 변 집합의 순서쌍 로 표현.
그래프 에서
개의 꼭짓점에서 모든 꼭짓점의 쌍이 서로 인접한 그래프를 개의 꼭짓점을 가진 완전그래프,complete_graph라고 부르고, 으로 표시.[1]
주로 유한집합 를 생각해 그 원소들을 꼭짓점vertex이라고 부르고,
라는 의 원소들의 (순서가 없는) 쌍으로 이루어진 집합으로 생각해, 그 원소들을 변edge이라고 부르며, 그래프는 꼭짓점 집합과 변 집합의 순서쌍 로 표현.
그래프 에서
- 두 꼭짓점 사이에 변이 있으면,
- 즉 가 성립하면,
개의 꼭짓점에서 모든 꼭짓점의 쌍이 서로 인접한 그래프를 개의 꼭짓점을 가진 완전그래프,complete_graph라고 부르고, 으로 표시.[1]
Sub:
//from mathworld
k분그래프,k-partite_graph에서 k=2인 경우.
모든 acyclic_graph는 bipartite.
클릭,clique
완전그래프,complete_graph
완벽그래프,perfect_graph
평면그래프,planar_graph 평면성그래프?
단순그래프,simple_graph
simple_graph https://mathworld.wolfram.com/SimpleGraph.html
weighted_graph
cyclic_graph
acyclic_graph
cube_graph
트리,tree
pseudotree https://mathworld.wolfram.com/Pseudotree.html
이분그래프,bipartite_graph
{완전그래프,complete_graph
완벽그래프,perfect_graph
평면그래프,planar_graph 평면성그래프?
단순그래프,simple_graph
고리나 평행변을 갖지 않는 그래프.
simple_directed_graph
https://proofwiki.org/wiki/Definition:Simple_Graph
부분그래프,subgraph 부분그래프 서브그래프 ....중에?고리와 평행변은 (수학백과: 그래프) 참조
고리나 다중변을 갖지 않는 그래프.[2]simple_directed_graph
https://proofwiki.org/wiki/Definition:Simple_Graph
spanning_subgraph - writing
이 셋은 see https://terms.naver.com/entry.naver?docId=3404981&cid=47324&categoryId=47324
https://proofwiki.org/wiki/Definition:Subgraph
directed_graph 유향그래프 (有向グラフ ) 방향성그래프 ... 방향그래프?모든 vertex를 포함한 부분그래프,subgraph (wpko)
(대충) 원래 그래프와 노드는 같고, 일부 edge만 포함된. ... 그리고 모두 연결되어야? chk
mklink spanning_tree
신장_부분_그래프
https://proofwiki.org/wiki/Definition:Spanning_Subgraph 를 포면 graph의 factor라고도 한다는데. 저걸 번역한다면? 요소? 인자? chk
... spanning subgraph
유도된부분그래프,induced_subgraph(대충) 원래 그래프와 노드는 같고, 일부 edge만 포함된. ... 그리고 모두 연결되어야? chk
mklink spanning_tree
신장_부분_그래프
https://proofwiki.org/wiki/Definition:Spanning_Subgraph 를 포면 graph의 factor라고도 한다는데. 저걸 번역한다면? 요소? 인자? chk
... spanning subgraph
이 셋은 see https://terms.naver.com/entry.naver?docId=3404981&cid=47324&categoryId=47324
https://proofwiki.org/wiki/Definition:Subgraph
directed graph
edge가 방향성,directionality을 가지는 graph.
Sub: simple_directed_graph DAG,directd_acyclic_graph
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_graphedge가 방향성,directionality을 가지는 graph.
Sub: simple_directed_graph DAG,directd_acyclic_graph
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
edge가 방향성,directionality을 가지지 않고 연결,connection만을 하는 그래프.
undirected graph
번역tbd, 무향그래프 (無向グラフ ) 비방향성그래프 ....?
undirected_graph
https://xlinux.nist.gov/dads/HTML/undirectedGraph.html
https://mathworld.wolfram.com/UndirectedGraph.html
"undirected graph" undirected graph
quiver (writing)undirected graph
번역tbd, 무향그래프 (無向グラフ ) 비방향성그래프 ....?
undirected_graph
https://xlinux.nist.gov/dads/HTML/undirectedGraph.html
https://mathworld.wolfram.com/UndirectedGraph.html
"undirected graph" undirected graph
simple_graph https://mathworld.wolfram.com/SimpleGraph.html
weighted_graph
https://mathworld.wolfram.com/WeightedGraph.html - 가중값,weight이 branch에? branch 가 뭐지? edge 말하는거? - Yes.[3]
https://xlinux.nist.gov/dads/HTML/weightedGraph.html (edge-weighted graph)
weighted and directed graph
regular_graphhttps://xlinux.nist.gov/dads/HTML/weightedGraph.html (edge-weighted graph)
weighted and directed graph
https://mathworld.wolfram.com/RegularGraph.html
https://freshrimpsushi.github.io/posts/regular-graph/
순환그래프,cycle_graph = circuit_graph - goto 순환,cycle#s-4https://freshrimpsushi.github.io/posts/regular-graph/
cyclic_graph
acyclic_graph
순환,cycle 없는?
Sub:
DAG,directed_acyclic_graph
https://mathworld.wolfram.com/AcyclicGraph.html - graph_cycle(순환,cycle)이 없는. 이건 bipartite_graph 임.
unicyclic_graphSub:
DAG,directed_acyclic_graph
https://mathworld.wolfram.com/AcyclicGraph.html - graph_cycle(순환,cycle)이 없는. 이건 bipartite_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용어사전
무방향그래프임.
무방향그래프임.
Twins:
IT용어사전: 이분 그래프
수학백과: 이분그래프
https://mathworld.wolfram.com/BipartiteGraph.html
이분_그래프
Bipartite_graph - aka bigraph
https://encyclopediaofmath.org/wiki/Graph,_bipartite
IT용어사전: 이분 그래프
수학백과: 이분그래프
https://mathworld.wolfram.com/BipartiteGraph.html
이분_그래프
Bipartite_graph - aka bigraph
https://encyclopediaofmath.org/wiki/Graph,_bipartite
Complete_bipartite_graph - aka biclique
완전_이분_그래프 - 정의에 집합의_분할,set_partition 언급됨.
https://mathworld.wolfram.com/CompleteBipartiteGraph.html
완전_이분_그래프 - 정의에 집합의_분할,set_partition 언급됨.
https://mathworld.wolfram.com/CompleteBipartiteGraph.html
See also:
https://mathworld.wolfram.com/CompleteTripartiteGraph.html 완전삼분그래프
https://mathworld.wolfram.com/Completek-PartiteGraph.html 완전k분그래프
Up: 완전그래프,complete_graph 이분그래프,bipartite_graph
}
https://mathworld.wolfram.com/CompleteTripartiteGraph.html 완전삼분그래프
https://mathworld.wolfram.com/Completek-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
singleton_graph
labeled_graph
해밍_그래프,Hamming_graph w
path_graph = linear_graphconnected_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_graphempty_graph를 뜻하기도 하고, node가 0개, edge가 0개인 그래프를 뜻하기도 함. https://mathworld.wolfram.com/NullGraph.html
Null_graph - may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
https://proofwiki.org/wiki/Definition:Null_Graph
edgeless_graphNull_graph - may refer either to the order-zero graph, or alternatively, to any edgeless graph (the latter is sometimes called an "empty graph").
https://proofwiki.org/wiki/Definition:Null_Graph
singleton_graph
labeled_graph
See also weighted_graph
https://mathworld.wolfram.com/LabeledGraph.html
https://xlinux.nist.gov/dads/HTML/labeledgraph.html
Eulerian_graph Euler_graphhttps://mathworld.wolfram.com/LabeledGraph.html
https://xlinux.nist.gov/dads/HTML/labeledgraph.html
해밍_그래프,Hamming_graph w
Path_graph
경로_그래프 "는 모든 꼭짓점의 차수가 2 이하인 나무"
mklink: 경로,path와? < Up: 경로,path 그래프,graph 인가? >
https://mathworld.wolfram.com/PathGraph.html
(주의 linear_graph 말고 line_graph 는 별도)
sparse_graph
dense_graph
(대충) 이건 특정한 그래프는 아니고 연결된 정도의 밀도,density에 따른 분류인데 둘을 나누는 명확한 기준은 없으며, node의 수와 edge의 수를 비교하여 상대적으로 정해지는? CHK
dense_graph
(대충) 이건 특정한 그래프는 아니고 연결된 정도의 밀도,density에 따른 분류인데 둘을 나누는 명확한 기준은 없으며, node의 수와 edge의 수를 비교하여 상대적으로 정해지는? CHK
graph_complement or complement_graph or complementary_graph - writing
////그래프관련주제////
두 그래프 G, H의 강한 곱, 강한곱, 강곱?
그래프색칠,graph_coloring - notes.txt에 작성중
그래프순회,graph_traversal - 현재 notes.txt =순회,traversal 에 작성중
그래프동형 graph_isomorphism ?? 수학백과: 그래프 동형
독립집합,independent_set - curr goto 독립성,independence#s-8
강한곱,strong_product
{그래프순회,graph_traversal - 현재 notes.txt =순회,traversal 에 작성중
그래프동형 graph_isomorphism ?? 수학백과: 그래프 동형
독립집합,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에서 가져오면,
codecogs에서 가져오면,
See https://horizon.kias.re.kr/17100/ 중간쯤 ('램지 이론 활용의 예' 문단) "이때 두 그래프"
{
그래프,graph의 강한곱,strong_product의 독립수,independence_number를 램지_수,Ramsey_number를 써서 계산 가능.
{
그래프,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
Strong_product_of_graphs - aka normal_product, AND_product
strong.product
https://mathworld.wolfram.com/GraphStrongProduct.html
Strong_product_of_graphs - aka normal_product, AND_product
strong.product
Up: 이항연산,binary_operation? 그래프곱,graph_product
}
{
Sub:
https://mathworld.wolfram.com/GraphProduct.html
https://www2.ccs.neu.edu/research/demeter/design-decisions/traversal-strategies/products/Graph%20Product%20--%20from%20MathWorld.htm
Graph_product
}
}
{
Sub:
graph_Cartesian_product
categorical product
graph lexicographic product
graph strong product
Twins:categorical product
graph lexicographic product
graph strong product
https://mathworld.wolfram.com/GraphProduct.html
https://www2.ccs.neu.edu/research/demeter/design-decisions/traversal-strategies/products/Graph%20Product%20--%20from%20MathWorld.htm
Graph_product
}
graph_likelihood /// 가능도,likelihood에 있었는데 가능도가 아니라 닮음정도 닮음도 같은 거 같아서 여기로 가져옴
{
https://mathworld.wolfram.com/GraphLikelihood.html
그래프,graph 단순그래프,simple_graph
}
{
https://mathworld.wolfram.com/GraphLikelihood.html
그래프,graph 단순그래프,simple_graph
}
Contents
- 1. 구성: 필수적인 요소
- 2. 구성: optional한 요소
- 3. 용어
- 4. 분류 TODO 위쪽 Sub: 로 옮길 것
- 5. 관련? TBW: 어떤관계?
- 6. topics
- 7. graph theory: 그래프 관련 알고리듬,algorithm
- 8. 그래프의 자료구조,data_structure 표현
- 9. 그래프의 일반화
- 10. 학습 도움 사이트 - 시각화visualization ....
- 11. 참고 tmp links ko
- 12. 기타
- 13. TBD: 그래프와 네트워크의 관계
- 14. Twins
- 15. Etc 1 (보통, 이산수학/조합론/CS/graph_theory 제외한 수학에서 일컫는 그래프) 함수의 그래프 + 음함수의 그래프
- 16. Etc 2 (통계자료의 시각화 등에 쓰이는 그래프)
- 17. Etc 3 (logic - 이것도 논리학에서 시각화를 위한?) logical graph
- 18. Etc 4 - knowledge graph
- 19. Etc 5 - graph database
1. 구성: 필수적인 요소 ¶
가장 기본적인 두가지부터 어휘 및 그 번역어가 너무 다양. (주의. 이 학문은 수많은 graph 종류의 정의부터도 책에 따라 조금씩 다른 경우가 많음. TODO 예시 추가)
대충 같이 쓰이는 쌍을 좀 분류하면
graph_vertex
https://mathworld.wolfram.com/GraphVertex.html
graph_edge
https://mathworld.wolfram.com/GraphEdge.html
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
https://proofwiki.org/wiki/Definition:Vertex_Set
edge_set
https://proofwiki.org/wiki/Definition:Edge_Set
// 집합,set
2. 구성: optional한 요소 ¶
weight - 가중값,weight, 있으면 weighted_graph
edge의 성질.
ex. vertex 간을 이동하는 시간, 이동하는 비용...
방향성 directionality - 있는지 여부에 따라 나뉨. directed_graph vs undirected_graphex. vertex 간을 이동하는 시간, 이동하는 비용...
edge의 성질.
3. 용어 ¶
차수 degree - degree of a vertex
connected - 직간접적으로 연결된 .... ??? CHK
node의 성질.
한 node에 연결된 edge의 수.
한 vertex에 연결된 edge의 개수.
directed_graph/undirected_graph에 따라 용어가 달라짐.
수학백과: 꼭짓점의 차수
https://freshrimpsushi.github.io/posts/degree-in-graph-theory/
유향그래프의 경우한 node에 연결된 edge의 수.
한 vertex에 연결된 edge의 개수.
directed_graph/undirected_graph에 따라 용어가 달라짐.
undirected일 때는 그냥 degree.
directed일 때는 indegree / outdegree.
꼭짓점의 차수(degree of a vertex)는 해당 꼭짓점과 결합하고 있는 변의 개수를 뜻한다.[4]directed일 때는 indegree / outdegree.
수학백과: 꼭짓점의 차수
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가 존재하면 이것들은 인접.출력차수 out-degree : node에서 나가는 edge의 수 // https://xlinux.nist.gov/dads/HTML/outdegree.html
즉 두 node(vertex)의 성질.
adjacent - 직접연결된connected - 직간접적으로 연결된 .... ??? CHK
incident/adjacent, incidence/adjacency
고리(loop) : 양 끝점이 같은 변
링크(link) : 양 끝점이 서로 다른 변
see 그림 2 at 수학백과 '고리와 링크'
두 node가 한 edge로 연결되어 있을 경우,
고리와 링크 - 변의 두 분류이 두 nodes는 adjacent(인접).
그리고 이 edge는 두 nodes에 incident(부속). (김황남, via ratsgo)
그리고 이 edge는 두 nodes에 incident(부속). (김황남, via ratsgo)
고리(loop) : 양 끝점이 같은 변
링크(link) : 양 끝점이 서로 다른 변
see 그림 2 at 수학백과 '고리와 링크'
평행변(parallel edges) 또는 다중변(multiple edges) : 끝점들의 짝이 같은 두 개 이상의 링크들
see 수학백과 '평행변'
see 수학백과 '평행변'
보행 walk https://mathworld.wolfram.com/Walk.html
경로,path : node가 중복되지 않는 trail
닫힌 트레일 closed trail - 일부 저자들은 이걸 회로,circuit 또는 여행,tour이라고도 한다
순환,cycle : closed path 닫힌 경로 - 닫힌경로,closed_path
그래프 전체를 거치는 walk
연결그래프 connected graph
비연결그래프 disconnected graph
연결성분 connected component
오일러 지표 Euler characteristic = 오일러_지표 - homology? - 종수,genus 언급. genus가 0인 그래프는 평면그래프,planar_graph.
오일러 지표 Euler characteristic - homology? - 종수,genus 언급. genus가 0인 그래프는 평면그래프,planar_graph.
....불변량,invariant
해밀턴_보행? 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는 다른 것임)
경로_(그래프_이론)
닫힌 보행 closed walk : 시작node와 끝node가 같은 walkhttps://mathworld.wolfram.com/GraphPath.html
(path_graph는 다른 것임)
경로_(그래프_이론)
같은 node를 거듭해서 거치지 않는 edge들의 sequence.
유향그래프에서는 유향경로(=방향경로=dipath)가 있음.
단순경로 : 처음node와 끝node를 제외하고 중복된 정점이 없는 경로(???)
Path_(graph_theory)유향그래프에서는 유향경로(=방향경로=dipath)가 있음.
단순경로 : 처음node와 끝node를 제외하고 중복된 정점이 없는 경로(???)
닫힌 트레일 closed trail - 일부 저자들은 이걸 회로,circuit 또는 여행,tour이라고도 한다
순환,cycle : closed path 닫힌 경로 - 닫힌경로,closed_path
그래프 전체를 거치는 walk
Eulerian_trail : 모든 edge가 정확히 한 번씩 포함된 closed trail. (node가 중복될 수 있어, path는 아니라고..)
해밀턴_경로,Hamiltonian_path : 모든 node를 정확히 한 번씩 거치는 path.
부분그래프 subgraph 서브그래프해밀턴_경로,Hamiltonian_path : 모든 node를 정확히 한 번씩 거치는 path.
비교: 오일러_경로,Eulerian_path - Eulerian_path or Euler_path
해밀턴_경로
Hamiltonian_path
Hamiltonian_path
경로,path
Hamiltonian_cycle 해밀턴_순환 ? : 시작node와 끝node가 같은 Hamiltonian_path.
해밀턴_경로
Hamiltonian_path
Hamiltonian_path
경로,path
Hamiltonian_cycle 해밀턴_순환 ? : 시작node와 끝node가 같은 Hamiltonian_path.
클릭,clique
생성나무,spanning_tree = 신장 부분 그래프 spanning subgraph - 신장_부분_그래프
유도부분그래프 induced subgraph
그래프_마이너 - edge를 contraction시켜 얻는 graph. // edge_contraction
이걸 일반화시키면 matroid_minor - see 매트로이드,matroid.
// 위상,topology수학적 성질은..생성나무,spanning_tree = 신장 부분 그래프 spanning subgraph - 신장_부분_그래프
유도부분그래프 induced subgraph
그래프_마이너 - edge를 contraction시켜 얻는 graph. // edge_contraction
이걸 일반화시키면 matroid_minor - see 매트로이드,matroid.
연결그래프 connected graph
비연결그래프 disconnected graph
연결성분 connected component
오일러 지표 Euler characteristic = 오일러_지표 - homology? - 종수,genus 언급. genus가 0인 그래프는 평면그래프,planar_graph.
오일러 지표 Euler characteristic - homology? - 종수,genus 언급. genus가 0인 그래프는 평면그래프,planar_graph.
....불변량,invariant
// 크기 척도
두 node 사이의 거리,distance
지름,diameter : 최대 이심률
//이상 geometry 용어 재활용함을 볼 수 있음.
가중그래프 weighted graph - edge에 가중값,weight이 주어진 그래프.
// 이상 주로 용어 그래프_이론_용어 참고하여 기본적 골격, chk
두 node 사이의 거리,distance
경로가 없으면 길이 무한대,infinity
이심률,eccentricity지름,diameter : 최대 이심률
//이상 geometry 용어 재활용함을 볼 수 있음.
가중그래프 weighted graph - edge에 가중값,weight이 주어진 그래프.
// 이상 주로 용어 그래프_이론_용어 참고하여 기본적 골격, chk
4. 분류 TODO 위쪽 Sub: 로 옮길 것 ¶
단순그래프 simple graph
{ chk
두 node를 연결하는 ..(edge?)..가 최대 하나. 둘 이상이면 x. 또는 한 node에서 자기 자신으로 가는 루프,loop가 있어도 x.
{ 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://proofwiki.org/wiki/Definition:Loop_(Graph_Theory) / https://proofwiki.org/wiki/Definition:Loop-Graph )
유향그래프 방향성그래프 directed_graph = digraph - edge가 방향이 있음
무향그래프
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/Multigraph.html
https://ncatlab.org/nlab/show/multigraph
https://proofwiki.org/wiki/Definition:Multigraph
https://xlinux.nist.gov/dads/HTML/multigraph.html
유향그래프 방향성그래프 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 : 유향 그래프 변이나 정점에 가중치 정보가 추가된 그래프 가중_그래프
간선 가중 그래프 edge-weighted_graph : 변에 가중치를 나타낸 그래프
정점 가중 그래프 vertex-weighted_graph : 정점에 가중치를 나타낸 그래프
네트워크,network : = 가중 그래프
// 처음배우는인공지능 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 : = 가중 그래프
무한그래프,infinite_graph
#linegraph
선그래프,line_graph
https://mathworld.wolfram.com/LineGraph.html
(주의: linear_graph 는 별도의 개념)
#linegraph
선그래프,line_graph
https://mathworld.wolfram.com/LineGraph.html
(주의: linear_graph 는 별도의 개념)
ADDHERE
Sub:
5. 관련? TBW: 어떤관계? ¶
트리,tree : 출발점이 되는 정점(루트,root)가 있는 그래프의 일종
B-트리,B-tree
온톨로지,ontology - 데이터의 관계를 나타내는 요소를 추가한 트리
정확한 정의는 TBW
이진_탐색_트리,binary_search_treeB-트리,B-tree
온톨로지,ontology - 데이터의 관계를 나타내는 요소를 추가한 트리
6. topics ¶
순환,cycle
경로,path
경로,path
최단경로,shortest_path ... kw: pathfinding, path_finding
순회,traversal : algorithm. 트리,tree에도 적용됨.최단경로문제,shortest_path_problem - 최단경로 페이지에서 이걸 분리할 필요가 있나?
최단_경로_문제
최단_경로_문제
플로이드-워셜_알고리즘 (edge의 weight가 ...) 인 weighted_graph에서 최단경로들을 찾.
Floyd–Warshall_algorithm
데이크스트라_알고리즘
벨먼-포드_알고리즘
A*_알고리즘
Floyd–Warshall_algorithm
데이크스트라_알고리즘
벨먼-포드_알고리즘
A*_알고리즘
그래프 곱 graph_product - see 곱,product
↑↓ QQQ 이 둘 관련이? 같은거??
Cartesian_product_of_graphs
QQQ
이건 본질적 구조와 연결상태가 중요하고 시각화했을때의 생김새는 전혀 중요하지 않다는거 그건가? or not? ... 그렇다면 위상,topology적인 주제? CHK
rel. 동형사상,isomorphism
그래프_동형_사상
Graph_isomorphism
QQQ
cartesian product는 product set(곱집합,product_set)이라고도 하는데, 그럼
cartesian product of graphs도 product set of graphs라고 할 수 있는지?
그래프동형,graph_isomorphism or 그래프동형사상? 동형그래프 isomorphic_graph ... 관련 문제,problem - 그래프동형문제cartesian product of graphs도 product set of graphs라고 할 수 있는지?
이건 본질적 구조와 연결상태가 중요하고 시각화했을때의 생김새는 전혀 중요하지 않다는거 그건가? or not? ... 그렇다면 위상,topology적인 주제? CHK
rel. 동형사상,isomorphism
그래프_동형_사상
Graph_isomorphism
7. graph theory: 그래프 관련 알고리듬,algorithm ¶
//TODO 위 문단과 합칠것.
순회,traversal
깊이우선탐색,depth-first_search,DFS
너비우선탐색,breadth-first_search,BFS
최적 탐색 optimal search
최선 우선 탐색 best-first search
에이스타? A스타? A* algorithm
미니맥스 원리 mini-max minimax 미니맥스_원리
알파베타가지치기,alpha-beta_pruning
깊이우선탐색,depth-first_search,DFS
너비우선탐색,breadth-first_search,BFS
최적 탐색 optimal search
최선 우선 탐색 best-first search
에이스타? A스타? A* algorithm
미니맥스 원리 mini-max minimax 미니맥스_원리
알파베타가지치기,alpha-beta_pruning
8. 그래프의 자료구조,data_structure 표현 ¶
표현,representation 방법 두가지:
sparse_graph 에는 adjacency 리스트,list가
dense_graph 에는 adjacency 행렬,matrix이 좋다
- 인접리스트,adjacency_list representation // https://xlinux.nist.gov/dads/HTML/adjacencyListRep.html
- 인접행렬,adjacency_matrix representation // https://xlinux.nist.gov/dads/HTML/adjacencyMatrixRep.html
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을 빼준 것.
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 : 정점 사이 관계를 나타내는 행렬. 인접행렬
근접행렬,incidence_matrix : 정점과 변의 관계를 나타내는 행렬 Incidence_matrix
근접행렬,incidence_matrix : 정점과 변의 관계를 나타내는 행렬 Incidence_matrix
9. 그래프의 일반화 ¶
그래프는 edge가 정확히 2개의 vertex만 만날(join) 수 있는데, 하이퍼그래프,hypergraph는 개수 제한이 없다. (WpEn) (보면 여러 정점들을 거치는 것을 볼 수 있음.)
https://xlinux.nist.gov/dads/HTML/hypergraph.html
Hypergraph
"A graph whose hyperedges connect two or more vertices."
hyperedge : https://xlinux.nist.gov/dads/HTML/hyperedge.html
하이퍼그래프hyperedge : https://xlinux.nist.gov/dads/HTML/hyperedge.html
Hypergraph
12. 기타 ¶
성냥개비 그래프(matchstick graph) - 취미 수학 영역?
평면에 펼쳐 놓은, 두 점을 연결하는 선이 모두 길이가 같은 선분인 그래프
365일 수학: 3-정규 성냥개비 그래프
평면에 펼쳐 놓은, 두 점을 연결하는 선이 모두 길이가 같은 선분인 그래프
365일 수학: 3-정규 성냥개비 그래프
13. TBD: 그래프와 네트워크의 관계 ¶
위에 여러 sources를 통해 써놓은 거 보면 그래프 중
둘을 완전히 구분하는 것은 불가능.
graph가 좀더 뜻이 일반적인 듯.
어떤 내용을 graph에, 어떤 내용을 network에 주로 적을지 TBD.
- 유향그래프가 네트워크라는 곳도 있고
- 유향 가중그래프가 네트워크라는 곳도 있고
- (그 외에) 동의어로 서술한 곳도 있다.
둘을 완전히 구분하는 것은 불가능.
graph가 좀더 뜻이 일반적인 듯.
어떤 내용을 graph에, 어떤 내용을 network에 주로 적을지 TBD.
이 둘의 sub:
그리고
그래프의 다른 뜻: 함수 등을 시각화한 것 (이 페이지 아래쪽)
네트워크의 다른 뜻: 통신,communication 등에 쓰이는 프로토콜,protocol 규칙을 따르는 그거. (sub: computer_network? 네트워크프로그래밍,network_programming 네트워크보안,network_security etc)
그리고
그래프의 다른 뜻: 함수 등을 시각화한 것 (이 페이지 아래쪽)
네트워크의 다른 뜻: 통신,communication 등에 쓰이는 프로토콜,protocol 규칙을 따르는 그거. (sub: computer_network? 네트워크프로그래밍,network_programming 네트워크보안,network_security etc)
14. Twins ¶
수학백과: 그래프
수학백과: 그래프 이론 (본문은 주로 역사. 끝부분 '같이 읽기'에 여러 주제들 있으니 참조.)
수학백과: 그래프 이론 주요 용어
그래프_이론
두산백과: 그래프 이론
수학백과: 그래프 이론 (본문은 주로 역사. 끝부분 '같이 읽기'에 여러 주제들 있으니 참조.)
수학백과: 그래프 이론 주요 용어
그래프_이론
두산백과: 그래프 이론
tmp:
https://everything2.com/title/graph
https://everything2.com/title/graph theory
수학에서의 그래프와 네트워크 https://freshrimpsushi.github.io/posts/graph-and-network-in-mathematics/
https://everything2.com/title/graph
https://everything2.com/title/graph theory
수학에서의 그래프와 네트워크 https://freshrimpsushi.github.io/posts/graph-and-network-in-mathematics/
15. Etc 1 (보통, 이산수학/조합론/CS/graph_theory 제외한 수학에서 일컫는 그래프) 함수의 그래프 + 음함수의 그래프 ¶
graph of an equation?
graph of a function? 함수,function
집합을 만족하는 좌표 점을 좌표평면에 그린 것??
별도의 페이지로 분리한다면 pagename은? 함수그래프,function_graph?
graph of a function? 함수,function
집합을 만족하는 좌표 점을 좌표평면에 그린 것??
별도의 페이지로 분리한다면 pagename은? 함수그래프,function_graph?
보통 // 독립변수와_종속변수
가로축에 독립변수,independent_variable를,
세로축에 종속변수,dependent_variable 나타냄
수평축/가로축/x축
수직축/세로축/y축
가로축에 독립변수,independent_variable를,
세로축에 종속변수,dependent_variable 나타냄
수평축/가로축/x축
수직축/세로축/y축
보통 그리는 법(sketching a graph): // 대략적으로
절편(intercept)들을 표시한다.
방정식을 만족하는 점들의 좌표를 구해 평면에 찍고(plot) 점들을 곡선으로 부드럽게 잇는다.
절편(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.) 의 그래프를 곡면,surface 라고도 부른다.
(Thomas)
}
즉 2D에서 그래프는 곡선, 3D에서 그래프는 곡면, nD에서 그래프는 (...) ...? chk
}
즉 2D에서 그래프는 곡선, 3D에서 그래프는 곡면, nD에서 그래프는 (...) ...? chk
표현
graphing n. 그래프 그리기
graphing n. 그래프 그리기
주제:
점근선,asymptote
플롯,plot - 비슷
drawing_graph or graph_drawing or plotting? (아마 플롯,plot 그리기도 동의어) 이런거
{
gnuplot
맷플럿립,Matplotlib - 파이썬,Python으로는 이걸 많이
}
점근선,asymptote
플롯,plot - 비슷
drawing_graph or graph_drawing or plotting? (아마 플롯,plot 그리기도 동의어) 이런거
{
gnuplot
맷플럿립,Matplotlib - 파이썬,Python으로는 이걸 많이
}
17. Etc 3 (logic - 이것도 논리학에서 시각화를 위한?) logical graph ¶
logical_graph
logical graph
번역? 논리그래프 - 가 최선?
logical graph
번역? 논리그래프 - 가 최선?
19. Etc 5 - graph database ¶
graph_database
graph database
graph database
Twins:
https://ncatlab.org/nlab/show/graph
https://proofwiki.org/wiki/Definition:Graph_(Graph_Theory)
https://ncatlab.org/nlab/show/graph
https://proofwiki.org/wiki/Definition:Graph_(Graph_Theory)
----
- [1] https://horizon.kias.re.kr/17100/ "자연수 집합 이외에도"
- [2] https://terms.naver.com/entry.naver?docId=3338375&cid=47324&categoryId=47324 비징의 정리
- [3] https://mathworld.wolfram.com/GraphEdge.html
- [4] 수학백과: 그래프
- [5] https://m.blog.naver.com/minichuuuuu/220808115381
- [6] MathWorld Multigraph