SKKU Matrix Lab : Project

<b><p>List of Contents</p></b>
<ul>
<li><a href="#1">Definition of Graph </a></li>
<li><a href="#2">Graph Isomorphism </a></li>

<li><a href="#3">Subgraph </a></li>
<li><a href="#4" >Vertex Degree </a></li>
<li><a href="#5" >Handshaking lemma </a></li>
<li><a href="#6" >path, walk, trail, cycle</a></li>
<li><a href="#7" >Vertex Connectivity </a></li>
<li><a href="#8" >Edge Connectivity </a></li>
<li><a href="#9" >Connected and Disconnected Graphs </a></li>
<li><a href="#10" >Distance </a></li>
<li><a href="#11" >Finding maximum(minimum) Wiener Index among Trees</a></li>
<li><a href="#12" >Vertex Coloring </a></li>
<li><a href="#13" >Edge Colorings </a></li>
<li><a href="#14" >Special Graphs </a></li>
<li><a href="#15" >Eulerian Graph </a></li>
<li><a href="#16" >Hamiltonian graphs </a></li>
<li><a href="#18" >Laplacian Matrix </a></li>
<li><a href="#19" >Characteristic polynomial of Graph </a></li>
<li><a href="#20" >The spectrum of a graph </a></li>
<li><a href="#21" >Star graph with n vertices </a></li>
</ul>

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

Graph is an ordered pair G = (VE) 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 simpleOrder of a graph G is the number of vertices and size of graph G is the number of edges of G.

# Graph Isomorphism    그래프 동형   http://en.wikipedia.org/wiki/Graph_isomorphism

An  isomorphism of graphs G and H is a bijection between the vertex sets of G and H $f \colon V(G) \to V(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

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.

EXAMPLE:

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 $v$ is denoted $\deg(v).$ 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.

## Handshaking lemma                핸드 쉐이킹 보조 정리                      http://en.wikipedia.org/wiki/Degree_(graph_theory)

The degree sum formula states that, given a graph $G=(V, E)$, $\sum_{v \in V} \deg(v) = 2|E|\, .$

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. 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.

EXAMPLE:

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

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

bridge, or cut edge or isthmus, is an edge whose removal disconnects a graph. (For example, all the edges in a tree are bridges.)

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

# Distance:       거리               http://en.wikipedia.org/wiki/Glossary_of_graph_theory

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 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.

For Example:

Basic structures

Small Graphs

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 ...)

Chessboard Graphs

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.

An Eulerian graph is a graph containing an 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              그래프의 행렬 표현

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 $L:=(\ell_{i,j})_{n \times n}$ is defined as: $L = D - A.$

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: $\ell_{i,j}:= \begin{cases} \deg(v_i) & \mbox{if}\ i = j \\ -1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise} \end{cases}$

where deg(vi) is degree of the vertex i.

# Characteristic polynomial of Graph                                   그래프의 특성 다항식                                                                       http://en.wikipedia.org/wiki/Characteristic_polynomial

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