SKKU Matrix Lab : Project
Made by SGLee and Ahmed
List of Contents
graph쉽게 이야기하면 변(edge)이라고 불리는 것들에 의하여 연결된 꼭지점들의 유한 집합이다. 좀 더 정확히 정의하면, 단순 그래프(simple graph)란 V라는 꼭지점의 집합과 V의 서로 다른 두 원소로 이루어진 집합들의 집합 E로 이루어진 순서쌍 (V,E)를 의미한다.
모든 그래프가 다 단순 그래프는 아니다. 때때로 두 개의 꼭지점들이 여러 개의 변들(multiple edges)로 연결될 수도 있고, 한 꼭지점이 자기 자신과 고리(loop)라는 변에 의하여 연결될 수도 있다. 경우에 따라서 그래프를 multigraph (멀티그래프)로 단순 그래프를 그래프(graph)로 부를 때도 있다. 그래프의 각 변에 방향을 줄 수 있는데 이렇게 하여 생긴 그래프를 유향그래프(digraph 또는 directed graph)라고 부른다.
WHAT IS A GRAPH? http://en.wikipedia.org/wiki/Graph_theory
A Graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes together with a set E of edges or lines, which are 2-element subsets of V (i.e., an edge is related with two vertices, and the relation is represented as an unordered pair of the vertices with respect to the particular edge). To avoid ambiguity, this type of graph may be described precisely as undirected and simple. Order of a graph G is the number of vertices and size of graph G is the number of edges of G.
An isomorphism of graphs G and H is a bijection between the vertex sets of G and H
such that any two vertices u and v of G are adjacent in G if and only if ƒ(u) and ƒ(v) are adjacent in H. This kind of bijection is commonly called "edge-preserving bijection", in accordance with the general notion of isomorphism being a structure-preserving bijection.
Subgraph 서브 그래프 http://en.wikipedia.org/wiki/Glossary_of_graph_theory
A subgraph of a graph G is a graph whose vertex set is a subset of that of G, and whose adjacency relation is a subset of that of G restricted to this subset.
A subgraph H is a spanning subgraph, or factor, of a graph G if it has the same vertex set as G. We say H spans G.
A subgraph H of a graph G is said to be induced (or full) if, for any pair of vertices x and y of H, xy is an edge of H if and only if xy is an edge of G. In other words, H is an induced subgraph of G if it has exactly the edges that appear in G over the same vertex set. If the vertex set of H is the subset S of V(G), then H can be written as G[S] and is said to be induced by S.
Vertex Degree 꼭지점 차수 http://en.wikipedia.org/wiki/Degree_(graph_theory)
Degree of a vertex of a graph is the number of edges incident to the vertex, with loops counted twice.The degree of a vertex is denoted The maximum degree of a graph G, denoted by Δ(G), and the minimum degree of a graph, denoted by δ(G), are the maximum and minimum degree of its vertices.
The degree sum formula states that, given a graph ,
The formula implies that in any graph, the number of vertices with odd degree is even. This statement (as well as the degree sum formula) is known as the handshaking lemma. The latter name comes from a popular mathematical problem, to prove that in any group of people the number of people who have shaken hands with an odd number of other people from the group is even.
path, walk, trail, cycle 한국 고교 교과서에서는 경로=trail 로 정의한다 GRAPH THEORY-Keijo Ruohonen-2013
A walk is a sequence , , , ..., of graph vertices and graph edges such that for , the edge has endpoints and . The length of a walk is its number of edges.
A walk is a trail if any edge is traversed at most once.
A trail is a path if any vertex is visited at most once except possibly the initial and terminal vertices when they are the same. A closed path is a circuit.
Vertex Connectivity 꼭지점 연결성 http://en.wikipedia.org/wiki/Glossary_of_graph_theory
A cut vertex is a vertex whose removal disconnects the remaining subgraph. A cut set, or vertex cut or separating set, is a set of vertices whose removal disconnects the remaining subgraph.
If it is always possible to establish a path from any vertex to every other even after removing any k - 1 vertices, then the graph is said to be k-vertex-connected or k-connected. Note that a graph is k-connected if and only if it contains k internally disjoint paths between any two vertices.
The vertex connectivity or connectivity κ(G) of a graph G is the minimum number of vertices that need to be removed to disconnect G.
Edge Connectivity 가장자리 연결성 http://en.wikipedia.org/wiki/Glossary_of_graph_theory
A bridge, or cut edge or isthmus, is an edge whose removal disconnects a graph. (For example, all the edges in a tree are bridges.)
A disconnecting set is a set of edges whose removal increases the number of components. An edge cut is the set of all edges which have one vertex in some proper vertex subset S and the other vertex in V(G)\S. Edges of K3 form a disconnecting set but not an edge cut. Any two edges of K3 form a minimal disconnecting set as well as an edge cut. An edge cut is necessarily a disconnecting set; and a minimal disconnecting set of a nonempty graph is necessarily an edge cut.
A graph is k-edge-connected if any subgraph formed by removing any k - 1 edges is still connected. The edge connectivity κ'(G) of a graph G is the minimum number of edges needed to disconnect G. One well-known result is that κ(G) ≤ κ'(G) ≤ δ(G).
The girth of a graph G, denoted g(G), is the length of a shortest cycle (if any) in G;
the circumference c(G) is the length of any longest cycle.
Connected and Disconnected Graphs 연결하거나 연결하지 않는 그래프 http://mathworld.wolfram.com/ConnectedGraph.html
A graph which is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph. A graph that is not connected is said to be disconnected.
The eccentricity of a vertex v in a connected graph G is the maximum graph distance between v and any other vertex u of G.
The radius of a graph is the minimum eccentricity of any vertex in a graph.
A shortest u- v path is called a u-v geodesic.
The diameter d(G) of a connected graph G is the length of any longest geodesic.
In chemical graph theory, the Wiener index (also Wiener number) is a topological index of a molecule, defined as the sum of the lengths of the shortest paths between all pairs of vertices in the chemical graph representing the non-hydrogen atoms in the molecule.
Finding maximum(minimum) Wiener Index among Trees 나무 사이에 최대 (최소) Wiener Index 찾기
Under code, finds maximum Wiener index among all trees on n vertices with a fixed diameter
Vertex Coloring 꼭지점 색칠 http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/coloring.htm
A k-coloring of G is an assignment of k colors to the vertices of G
in such a way that adjacent vertices are assigned different colors. If G has a k-coloring, then
G is said to be k-colorable.
The chromatic number of G, denoted by X(G), is the smallest number k for which is k-colorable.
Edge Colorings 가장자리 색칠 http://www.personal.kent.edu/~rmuhamma/GraphTheory/MyGraphTheory/coloring.htm
Let G be a graph with no loops. A k-edge-coloring of G is an assignment of k colors to the edges of G in such a way that any two edges meeting at a common vertex are assigned different colors,. If G has a k-edge coloring, then G is said to be k-edge colorable. The chromatic index of G, denoted by X`(G), is the smallest k for which G is k-edge-colorable.
Special Graphs 특별 그래프 http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph_generators.html#sage.graphs.graph_generators.GraphGenerators.LollipopGraph
Many graphs in SAGE can be drawn directly by their commands.
A small graph is just a single graph and has no parameter influencing the number of edges or vertices.
Platonic solids (ordered ascending by number of vertices)
Families of graphs
A family of graph is an infinite set of graphs which can be indexed by fixed number of parameters, e.g. two integer parameters. (A method whose name starts with a small letter does not return a single graph object but a graph iterator or a list of graphs or ...)
Eulerian Graph 오일러 참조 http://mathworld.wolfram.com/EulerianGraph.html
An Eulerian cycle, also called an Eulerian circuit, Euler circuit, Eulerian tour, or Euler tour, is a trail which starts and ends at the same graph vertex. In other words, it is a graph cycle which uses each graph edge exactly once.
Hamiltonian graphs 해밀턴 참조 http://mathworld.wolfram.com/HamiltonianCycle.html
A Hamiltonian cycle, also called a Hamiltonian circuit, Hamilton cycle, or Hamilton circuit, is a graph cycle (i.e., closed loop) through a graph that visits each node exactly once (Skiena 1990, p. 196). A graph possessing a Hamiltonian cycle is said to be a Hamiltonian graph.
Matrix Representation of Graphs 그래프의 행렬 표현
Adjacency Matrix 인접 행렬 http://mathworld.wolfram.com/AdjacencyMatrix.html
The Adjacency Matrix, sometimes also called the connection matrix, of a simple labeled graph is a matrix with rows and columns labeled by graph vertices, with a 1 or 0 in position according to whether and are adjacent or not. For a simple graph with no self-loops, the adjacency matrix must have 0s on the diagonal. For an undirected graph, the adjacency matrix is symmetric.
Laplacian Matrix 라플라스 행렬 http://en.wikipedia.org/wiki/Laplacian_matrix
Given a simple graph G with n vertices, its Laplacian matrix is defined as:
That is, it is the difference of the degree matrix D and the adjacency matrix A of the graph. In the case of directed graphs, either the indegree or outdegree might be used, depending on the application.
From the definition it follows that:
where deg(vi) is degree of the vertex i.
The characteristic polynomial of a graph is the characteristic polynomial of its adjacency matrix. It is a graph invariant, though it is not complete: the smallest pair of non-isomorphic graphs with the same characteristic polynomial have five nodes.
The spectrum of a graph 그래프의 스펙트럼 http://www.win.tue.nl/~aeb/2WF02/spectra.pdf
The (ordinary) spectrum of a ﬁnite graph Γ is by deﬁnition the spectrum of the
adjacency matrix A, that is, its set of eigenvalues together with their multiplicities.
The Laplace spectrum of a ﬁnite undirected graph without loops is the spectrum of
the Laplace matrix L.
Stargraph with n vertices