Math Modeling Project

Course : Seminar in algebraic and geometric modelling

Course Professor: Sung Gu Lee

Authors: Seyed Ahmad Mojallal and Shaowei Sun

List of Contents


Copyright @ 2014 SKKU Seminar in algebraic and geometric modelling Class.


그래프는 무엇인가?                                           http://matrix.skku.ac.kr/sglee/2003-1-NewFacTalk/2002-contents-Final/main/main.htm 

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

EXAMPLE:





path, walk, trail, cycle      한국 고교 교과서에서는 경로=trail 로 정의한다                        GRAPH THEORY-Keijo Ruohonen-2013       

 A walk is a sequence v_0e_1v_1, ..., v_k of graph vertices v_i and graph edges e_i such that for 1<=i<=k, the edge e_i has endpoints v_(i-1) and v_i. 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/p>

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

BullGraph CompleteMultipartiteGraph LadderGraph
ButterflyGraph DiamondGraph LollipopGraph
CircularLadderGraph EmptyGraph PathGraph
ClawGraph Grid2dGraph StarGraph
CycleGraph GridGraph ToroidalGrid2dGraph
CompleteBipartiteGraph HouseGraph Toroidal6RegularGrid2dGraph
CompleteGraph HouseXGraph  

Small Graphs

A small graph is just a single graph and has no parameter influencing the number of edges or vertices.

Balaban10Cage FranklinGraph MoebiusKantorGraph
Balaban11Cage FruchtGraph MoserSpindle
BidiakisCube GoldnerHararyGraph NauruGraph
BiggsSmithGraph GrayGraph PappusGraph
BlanusaFirstSnarkGraph GrotzschGraph PoussinGraph
BlanusaSecondSnarkGraph HallJankoGraph PetersenGraph
BrinkmannGraph HarriesGraph RobertsonGraph
BrouwerHaemersGraph HarriesWongGraph SchlaefliGraph
BuckyBall HeawoodGraph ShrikhandeGraph
CameronGraph HerschelGraph SimsGewirtzGraph
ChvatalGraph HigmanSimsGraph SousselierGraph
ClebschGraph HoffmanGraph SylvesterGraph
CoxeterGraph HoffmanSingletonGraph SzekeresSnarkGraph
DesarguesGraph HoltGraph ThomsenGraph
DoubleStarSnark HortonGraph TietzeGraph
DurerGraph KittellGraph Tutte12Cage
DyckGraph KrackhardtKiteGraph TutteCoxeterGraph
EllinghamHorton54Graph LjubljanaGraph TutteGraph
EllinghamHorton78Graph M22Graph WagnerGraph
ErreraGraph MarkstroemGraph WatkinsSnarkGraph
FlowerSnark McGeeGraph WellsGraph
FolkmanGraph McLaughlinGraph WienerArayaGraph
FosterGraph MeredithGraph  

Platonic solids (ordered ascending by number of vertices)

TetrahedralGraph HexahedralGraph DodecahedralGraph
OctahedralGraph IcosahedralGraph  

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

BalancedTree fusenes MycielskiStep
BarbellGraph FuzzyBallGraph NKStarGraph
BubbleSortGraph GeneralizedPetersenGraph NStarGraph
CirculantGraph HanoiTowerGraph OddGraph
cospectral_graphs HararyGraph PaleyGraph
CubeGraph HyperStarGraph RingedTree
DorogovtsevGoltsevMendesGraph JohnsonGraph SymplecticGraph
FibonacciTree KneserGraph trees
FoldedCubeGraph LCFGraph WheelGraph
FriendshipGraph line_graph_forbidden_subgraphs  
fullerenes MycielskiGraph  

Chessboard Graphs

BishopGraph KnightGraph RookGraph
KingGraph QueenGraph  










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


Konigsberg bridge





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








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 (v_i,v_j) according to whether v_i and v_j 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.







Star graph with n vertices      n 꼭지점을 갖는 스타 그래프            Made By Myself