1. No category

Introduction to
Mathematical Optimization
(Lecture #11)
Shunsuke HAYASHI
Today’s topic
Basic Knowledge of Graph Theory
（グラフ理論の基礎知識）
Graph
Graph is defined by a vertex set V and an edge set E.
vertex
edge
vertex set （頂点集合）
edge set （辺集合）
Note: Every edge can be written as a pair of two vertices, equivalently.
Vertex（頂点） is also called node（接点）, point（点）, etc.
Edge（辺） is also called link（リンク）, branch（枝）, arc（弧，弦）, etc.
3
Directed and Undirected Graphs
Undirected graph （無向グラフ）
Each edge does not have direction.
Directed graph （有向グラフ）
Each edge has direction.
4
Graph
Graph can visualize various systems.
5
Terminology （用語） 1
Graph A
Graph B
次数
The followings are defined only for “directed” graphs.
入次数
出次数
6
Terminology （用語） 2
Graph A
Graph B
self-loop（自己ループ）
multiple edge （多重辺）
7
Simple graph （単純グラフ）
simple graph
simple graph
a graph including neither self-loops
nor multiple edges
not simple graph
In the graph theory, many graphs are simple graphs.
8
Complete graph （完全グラフ）
complete graph
a graph having edges for any
pair of
complete graph
incomplete graph
9
Bipartite graph （２部グラフ）
bipartite graph
not bipartite graph
10
Bipartite graph is used for matching problem, etc.
Complete bipartite graph （完全２部グラフ）
complete bipartite graph
incomplete bipartite graph
Complete bipartite graph is not a complete graph in general.
Path and cycle of graph
is called a path (経路)
Example of path
Path can also be written by means of edges.
Length of path
number of edges in the path
12
Path and cycle of graph
is called a path (経路)
Example of path
elementary path （初等路）
simple path （単純路）
a path which does not use
the same vertices twice (or more)
a path which does not use
the same edges twice (or more)
13
Path and cycle of graph
is called a cycle (閉路)
Example of cycle
elementary cycle （初等閉路）
simple cycle （単純閉路）
a cycle which does not use
the same vertices twice (or more)
a cycle which does not use the same
edges twice (or more)
14
Subgraph and complement graph
subgraph （部分グラフ）
subgraph induced by
（
に誘導された部分グラフ）
15
Graph
Subgraph and complement graph
complement graph （補グラフ）
Notice: In considering the complement graph,
the original graph G must be simple.
Isomorphic graph
同形
Isomorphic graphs
17
Connectivity of undirected graph
（無向グラフの連結性）
(連結している)
def
同値関係
18
Connected components
(equivalent class (同値類) w.r.p.
)
If G consists of one connected components, then the graph is said to
be connected.
Graph with several connected
components
Connected graph
19
Tree and forest
Forest (森)
a graph having no cycle
Tree (木)
a connected forest
Leaf (葉)
a vertex in a tree/forest with degree 1
leaf
leaf
Forest
次数
Tree
20
Subtree and Spanning tree
Subtree (部分木)
Spanning tree (全域木)
21
Cut-set, cut, and minimal cut-set
22
Cut-set, cut, and minimal cut-set
23
Cut-set, cut, and minimal cut-set
真部分集合
極小カットセット
Cut-set, cut, and minimal cut-set
Theorem
Plane graph and Planar graph
(平面グラフと平面的グラフ）
Plane graph
Planar graph
plane graph
planar graph
non-planar graph
26
Plane partition by plane graph
A plane graph partitions a 2D plane naturally.
In other words, if a 2D plane is partitioned to several area,
then its adjacent relation can be drawn by a plane graph.
27
Seven Bridges in Königsberg
(ケーニヒスベルグの七つの橋）
Can we go across all the 7 bridges without duplication?
Königsberg (= Kaliningrad)
a city of Russia
Can we draw this without lifting
the brush from the paper?
No!
28
4 Colors problem
We want to put colors on each vertex so that any adjacent
vertices do not have the same color.
G
If G is a plane (or planar) graph, how many colors are need
at minimum?
The answer is 4.
This is equivalent with a well-known 4 colors problem.
(How many colors are needed to paint a map in
different colors?)
29