9512.net

# 2019年离散数学第3章图的基本概念.ppt_图文

() 2

3.1

1 VE<V,E>
G 2
3

4
5n
nnnm (n,m) 6
v() deg(v)v deg+(v)vdeg-(v)
deg(v) deg (v) deg (v) G(G)(G)

1

G
deg(v) 2 | E |
vV
[1]

[2]

1

G112233

44G

deg(v) 11 22 33 44 30 2 | E |,| E |15

2
G=<V,E> C

A) deg(V ) 2 | E | B) deg(V ) | E |

C) deg(v) 2 | E | D) deg(v) | E |

vV

vV

3 G12G21,
22343G :Gx3x-7 1 2 2 2 43 3(x 7) 212

x 9 ,G9
2 () n-1
3
G G

4

nKn

4

| E | n(n 1) 2

GnG

C

A) n(n-1) C) 1 n(n 1)
2

B) n(n+1) D) 1 (n 1)
2

5 GkG
k- 6
G GG G 7
G G G

5

V {a,b, c, d}GD

E(G) {(a, a),(a,b),(b,c),(a,c)}

E(D) { a,b , a,c , c, d , c, a , c,b }

GDGD

a

d

a

d

b

c

G

b

c

D

G deg(a) 4, deg(b) 2, deg(c) 2, deg(d) 0
D deg (a) 2, deg (a) 1, deg (b) 0, deg (b) 2 deg (c) 3, deg (c) 1, deg (d ) 0, deg (d ) 1
GD
8 1G=<V,E> V ' V , E' E
G'=<V',E'>G 2 V ' VE' EG'G 3V ' V , E' EG'G

GVG'V'
GG' G G'

1 G=<V,E>v0
vnv0vnv0vn v0vn v0vn
2

3

6

v1

G v1e5v5e7v2e2v3

e1

e5

v2

e6

v5

v5e6v2e2v3e3v4e8v2e7v5

e7

v2e7v5e6v2 v1e1v2e2v3e3v4e8v2e6v5

e2
v3

e8 e4
e3
v4

3.2

G G

GG G'G
G GW(G)

v2
G v1
v3

v5

v7

v4

v6

G

G({v1}) G({v2 , v3, v4 , v5}) G({v6, v7})
W (G) 3
{{v1},{v2 , v3, v4 , v5},{v6 , v7}} V

1
D (1) (2)
(3)

a

d

b

c

a

d

b

c

a

d

b

c

2 [6]
[7]

7
V{a,b,c,d},VE( A )
(A) {<a,b>,<a,c>,<d,a>,<b,d>,<c,d>} (B) {<a,d>,<b,a>,<b,c>,<b,d>,<d,c>} (C) {<a,c>,<b,a>,<b,c>,<d,a>,<d,c>} (D) {<a,d>,<b,a>,<b,d>,<c,d>,<d,c>}

1

G=<V,E>V'(

V')GV'V'

GV'V'G

V'

G

G v1

v4 v5

v1G1

v1

v4 v5

v2 W (G) 1v3

v2 W (G1) 1v3

v3G2

v1

v4

v1,v3G3

v5

v1

v4

v5

v2

v3

W (G2 ) 2

v2

v3

W (G3 ) 3

{v1}W(G1)=1

{v3}W(G2)=2

{v1,v3}

a

b

8 GG f

c

{ f }{c, e}

e

d

2 G=<V,E>E'
GE'E'GE E'GE'
G

G

v1

v4 v5

v2 W (G) 1v3

(v1,v2)G1

v1

v4 v5

v2 W (G1) 1v3

(v1,v2),(v2,v3)G2

v1

v4 v5

(v3,v5)G3

v1

v4

v5

v2

v3

v2

v3

W (G2 ) 2

W (G3 ) 2

{(v1,v2)}W(G1)=1 {(v1,v2),(v2,v3)}W(G2)=2 {(v3,v5)} W(G3)=2

3
()
GV'G
GV'()V'G
(G)

(1) GV'= (G) 0
(2) Gn-1
(Kn ) n 1 (3) G (G) 1 (4) G (G) 0

() GE'G
E'G (G)

(1) GE'=(G) 0 (2) G(G) 1 (3) G (G) 0 () (G), (G) (G) G (G) (G) (G)

3.3

G=<V,E>|V|=nnA(G)

aij viv j

G

e1 v1

v4

1 1 0 0 A(G) 1 0 1 0

e2

v2

e3

v3

0 1 0 0 0 0 0 0

A(G)

D=<V,E>|V|=nnA(D)

aij viv j A(D)

i vi

j v j

v1 D e1

e4

e3

0 1 1 A(D) 0 0 1

v2

e2

v3

1 0 0

9

D<V,E>

0 2 1 0

A(D)=

0 0

0 0

1 0

0 1

0 0 1 1

E 7

10

(D)= [aij ]n i
n

aij vi

j 1

A(D) aij1 aijA( D)

A2(D) a(ij2)2 aijA2 ( D)

Al (D)

a(l) l ij

aijAl (D)

aij viv j l
A(D)+A2(D)+ +Ak(D) aij

k a ij

viv

j

k

0 1 1 0 1 1 1 0 1
A2 (D) 0 0 1 0 0 1 1 0 0, aij 5
1 0 0 1 0 0 0 1 1
25v3v3 1 0 1 1 1 0 1 1 1 2
A(D) A2 (D) 0 0 1 1 0 0 1 0 1, aij 9
1 0 0 0 1 1 1 1 1
29

11

D=<V,E> v1

v4

Dv2v4

123

v2

v3

1 0 0 0

1 0 0 01 0 0 0 1 0 0 0

A(D) 2 0 1 0, A2 (D) 2 0 1 02 0 1 0 3 0 0 1

1 0 0 1

1 0 0 11 0 0 1 1 0 1 0

0 0 1 0

0 0 1 00 0 1 0 1 0 0 1

1 0 0 0 1 0 0 0 1 0 0 0

A3(D) 3 0 0 1 2 0 1 0 3 0 1 0 1 0 1 0 1 0 0 1 2 0 0 1

1 0 0 1 0 0 1 0 1 0 1 0

21 13

12

D

v1

v4

0 1 1 1 A(D) 1 0 1 0
0 1 0 1 1 0 1 0

v2

v3

v2v42v3v32 .

0 1 1 1 0 1 1 1 2 1 2 1

A2 (D) 1 0 1 0 1 0 1 0 0 2 1 2 a24 2

0 1

10 01

1 0 0 1

1 0

0 1

1 0

2 0

0 2

2 1

0 2

a33

2

2,v2v1v4 , v2v3v4v3v2v3, v3v4v3

13

D=<V,E> V {a1, a2 , a3 , a4 , a5}
E { a1, a2 , a2 , a4 , a3 , a1 , a4 , a5 , a5 , a2 }

D

D

0 1 0 0 0

0 0 0 1 0

(1) A(D) 1 0 0 0 0

0 0 0 0 1

0 1 0 0 0

(2) a3, a2a4a5 , a1a2 , a3a1,