Mathematical Programming（数理計画）

Mathematical Programming（数理計画）
Linear Programming
（線形計画）
Network optimization
（ネットワーク計画）
Discrete Optimization
（離散最適化）
Nonlinear Programming
（非線形計画）
Discrete Optimization（離散最適化）
• Combinatorial Optimization（組合せ最適化）
• Integer Programming （整数計画）
c.f. P1
Related Topics (関連分野)
•Linear Programming
•Graph Theory（グラフ理論）
•Algorithm and Date Structure
•Discrete Mathematics
Schedule
1.
2.
3.
4.
What is a graph?（グラフ基礎）
Shortest Path Problem（最短路問題）
Assignment Problem（割当問題）
Routing Problem（経路問題）
Graph（グラフ）- ?
90
80
70
60
50
40
30
20
10
0
東京
名古屋
大阪
1 月
2 月
3 月
4 月
Graph（グラフ）-examples
Graph -definition
V : vertex set（頂点集合）
A⊆V×V: arc set（枝集合）
vertex （頂点）
arc（枝）
G=(V, A)
discrete structure（離散構造）
Graph - sets vs illustration
V={a,b,c,d,e,f,g,h,i,j,k}
A={{a,b},{a,c},{a,e},{a,g},{b,c},{b,e},{b,f},
{c,d},{d,f},{d,g},{e,h},{e,k},{f,h},{f,j},
{g,j},{g,k},{h,i},{h,j},{i,j},{i,k},{j,k}}
a
e
b
ce
c
a
h
f
k
ii
g
d
j
g
b
d
f
h
j
k
Graph -examples
undirected graph（無向グラフ）
directed graph / digraph（有向グラフ）
Graph - digraph
V : vertex set（頂点集合）
A : arc set（枝集合）
ordered pairs of V
vertex （頂点）
arc（枝）
G=(V, A)
Digraph - sets vs illustration
b
V={a, b, c, d, e}
A={(a, b), (a, d), (b, c), (b, e), (c, a),
(c, e), (d, c), (c, e), (e, d)}
a
c
d
e
Graph - incidence
e
b
h
c
a
b
f
d
i
k
a
c
e
j
d
並列枝
(parallel)
g
• a とbは隣接(adjacent)
• 枝{a, b}はaに接続(incident)
• aとbは枝{a, b}の端点(end point) • aは枝(a, b)の始点(tail)
• bは枝(a, b)の終点(head)
2.1 基本的用語
グラフの言葉を覚えよう
e
Walk,trail,path
b
c
a
始点
(a,b, f, h, j, f, h, i, k)
(a, g, j, h, i, j, k)
(a, c, d, f, h, j, i, k)
f
d
walk trail path
(a, c, f, h, j, i, k)
h
i
k
終点
j
g
length=7
walk = 路
trail = 単純路
path = 道／初等的路
Closed walk,closed trail, e
cycle
b
h
c
a
f
d
i
j
c.walk c.trail cycle
(a, c, f, h, j, i, k,e,a)
(a,b, f, h, j, f, h, i, k,e,a)
(a, g, j, h, i, j, k,e,a)
(a, c, d, f, h, j, i, k,e,a)
g
walk = 路
trail = 単純路
path = 道／初等的路
k
Walk, trail, path - in digraph
b
forward
a
path directed path
(a,b,c,d,e)
(a,d,c,e)
(d,e,d)
c
backward
d
e
Subgraph（部分グラフ）
e
G=(V, A)
b
h
V’⊆V
G|V’
c
a
f
d
j
induced subgraph on V’
(V’が誘導する部分グラフ)
g
subgraph
i
k
Subgraph（部分グラフ）
e
G=(V, A)
spanning subgraph
（全域部分グラフ）
b
h
c
a
f
d
i
j
g
k
Subgraph（部分グラフ）
G=(V, A)
e
b
T⊆V
G\T
h
c
a
f
d
i
j
g
k
Connectivity （連結性）
not connected（非連結）
• connected component（連結成分）
• isolated vertex（孤立点）
connected（連結）
Connectivity - in digraph
strongly connected（強連結）
• root（根）
• strongly connected component
（強連結成分）
Degree（次
４
数）
３
４
４
４
３
４
３
４
３
４
Tree（木）
root
leaves（葉）
directed tree（有向木）
• forest
• spanning tree
Acyclic （非閉路） in digraph
not contain a directed cycle
Network（ネットワーク）
Graph + numerical data
capacity, cost, supply/demand…
2.2 基本性質
Fundamental Properties
グラフに慣れよう
Lemma2.1
Hand Shaking Lemma 握手補題
In any graph, the number of vertices of odd degree is even.
どんなグラフでも，奇数次数の頂点は偶数個ある．
Lemma2.1(proof)
In any graph, the number of vertices of odd degree is even.
どんなグラフでも，奇数次数の頂点は偶数個ある．
Σ(degree of v) = 2 |A|
v
the number of elements in A
⇒Σ(degree of v) is even
v
Lemma2.2
Let G be a graph having n vertices and let any vertex of G have
degree at least (n-1)/2. G must be connected.
n頂点のグラフGにおいて，どの頂点の次数も少なくとも
(n-1)/2であるとき，Gは連結である．
n=7
Lemma2.2(proof)
Let G be a graph having n vertices and let any vertex of G have
degree at least (n-1)/2. G must be connected.
n頂点のグラフGにおいて，どの頂点の次数も少なくとも
(n-1)/2であるとき，Gは連結である．
Assume that G has k connected components G1, G2, …, Gk.,
and each component Gi has ni vertices. Then,
n1+n2+…+nk=n.
For each component Gi, any vertices v in Gi has degree at most
ni-1. Thus we have,
(n-1)/2 ≦ni-1,
which implies that ni≧(n+1)/2. Hence k=1.
Lemma2.3
If G=(V, A) is not connected, the complementary graph G=(V, A) is connected.
Gが非連結のとき，その補グラフは連結である．
A= (V ×Ｖ)\A
G
G
Lemma2.3(proof)
If G=(V, A) is not connected, the complementary graph G=(V, A) is connected.
For a pair of vertices in any different components,
For a pair of vertices in a same component,
G
G
G2
G2
G1
connected component
G1
Gk
Gk
There is a path between any pair of vertices
Lemma2.4
Let G be a graph without isolated vertices having n vertices and n-1 arcs
(where n≧2). G contains at least two vertices of degree 1.
Gは孤立点をもたないグラフで，n個の頂点，n-1本の枝をもつ
とする．ただし， n≧2．このとき，Gは次数1の頂点を少なく
とも2つはもつ．
n=10
Σ(degree of v) = 2 (n-1)
v
degree
number
0
0
1
≦1
≧２
≧n-1
Σ(degree of v) ≧ 2 (n-1)＋1
v
Lemma2.5
Any connected graph on n vertices contains at least n-1 arcs.
(proof)
induction on n
v
Lemma2.6
Any acyclic graph on n vertices has at most n-1 arcs.
( a graph containing no cycle)
(proof)
induction on n
a
v
v’
Lemma2.7
(1) G is a tree
•connected
•acyclic
(4)
•connected
•removing any arc
from G becomes
unconnected.
(2)
•acyclic
•adding any arc to
G yields a cycle
(3)
•connected
•there is a unique
path between any
two vertices
(5)
•connected
•n-1 arcs
(n: number of
vertices)
(6)
•acyclic
•n-1 arcs

Download Report