Bài giảng : Lý thuyết đồ thị docx

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (530.65 KB, 78 trang )

 



 !"#$%&'()*+),
&-.-/,
C1
C3
C2
C4
C5
C7
C6
0*/1-,2*%3
4/56.7*+,5
 
8
(2
9!4"9!4 !-.:;
!<=-.-4
>4*5

?4@#$-/,A*
@


C1
C3
C2
C4
C5

C7
C6
6*4/#BC2*D4/
56.7+,8
&.#'5
 
EF/ G
#'
#'&'*
@H/∈!I(C:;4"H&
/#'H//
H/≠/H
%&'@H/J

H"%<

/"%

?@DH&/
x
y
 
EF/ K
#'
1
4
3
6
5
2







L/,
M2N2
?*L1
"L1
 
#'

?2.
O
#'&&

&
P
∈
Q

P
#$!"#$>&


Q
&

.

O
!%&>&
P


R9!4"N&"+#'>&

<#$#$
-,
O
Γ&

&Γ
ST
&


ΓHU/∈VH/∈W

Γ
EF/ X
 
#'
EF/ Y
 
EF/ Z
&.#'

&.#'&'*
@H/∈-.!I(C:;4"H

&/:DH/-.-[#'/
H//H
x
y
 
EF/ \
&.#'
1
2
3
4
5




*N2N2-/,]

ΓHU/∈VH/∈W
 
EF/ ^
+N%
1
2
3
4
5
40
70
60

20
50
10


6.
O
+#$/+N%
_*2`
O
#$4TN%

a.
O
4H* ωJ E R5

L ω@+#ợng ca e.
 
EF/ Tb
G5c5?493(8
L1

?2&@H/∈*%
"H&/5L@*:"
H/2 H/4"*@5L
H/#$"-1

d*-13e"
5
Q

Af&'H/&&/g7&
*-1
 
EF/ TT
L4C
x1
x2
x3
x4
x5
X1 và X2 là
hai đỉnh kề
nhau
X2 và X3 là
hai đỉnh kề
nhau
X1 và X4 là
hai đỉnh kề
nhau
 
EF/ Tc
h9>"

#'&&

∈
Q
=(I
O
+2=(9&2N%4-

e*/&2&

JA@
S
&

VΓ
ST
&

V
Q
=(I
O
2=(9+N%4-)
<D/+D&

JA@
i
&

VΓ&

V
Q
(I
O
>&

JA@&


A@
S
&

iA@
i
&


1
2
3
4
5
j=h9&2>TG
j=h9+>TT
 
h9>"

&.#'&&

∈
Q
(I
O
>&

JA@&


N%*-1&'&

+2
'
(
)$*+,&-'./

"(9b#$".9!

"(9T#$"+@2&
*'>#$*+@2
EF/ TG
 
h9>"
EF/ TK



"+@2
?*+@2
".9!
 
h9>"
EF/ TX
v
i
d
-
( v
i

) d
+
( v
i
) d( v
i
)
a 1 3 4
b 2 1 3
c 2 1 2
d 2 2 4
e 2 2 4
 
h9>"
EF/ TY
L
 
h9>"

M;,,
O
3"&*
Q
j#'7
Q

Q
M%"(I
O
kN%l

EF/ TZ
( ) ( )
i i
i i
v V v V
m d v d v
− +
∈ ∈
= =
∑ ∑
2 ( )
i
i
v V
m d v
∈
=
∑
 
G5G56N%A* (C
>&.#'L



E!&3c"(-m1.
O

*_">#$%84
"-4+2


6>"Nn*

6.
O
#'>&.
#'#:></>
( 1)
2
n n −
 

?2&05R(82
Q
%H:JH/∈/H∈
!8H:JH/∈/H∉5
Q
%H:>&3c"c
#$1
!8H:>/T&o
&3c"eT5L,
O
R


Q
8%H:/I(pA@
S
&



A@
i
&

∀&

∈
Q
-S1&
A@
S
&

A@
i
&

-∀&

∈
 

?2&.#'5R(82
Q
-S1&A@&

-q∀&

∈
Q



&'≥
"
T

c
r

&4*U
T

c
WU
c

G
W
rU
−T


W&U


T
W
 
Q
.

O
(4H@J

ST"&ST**2.
O
41

ST">1%T":)I45
Q
L,
O
s

 
Q
#t!I[!I2*

T

c
N22*>1%T
"+2
T
&'.
O
"+2
c

T


X

G

Y

K

c

T

c
#t!I
 
#t!I

j&"+2
T
1%&'
84"+2
c
7#t
!I>-FCL

&'V
T
V&V
c
V5`

O

(,
O
L
T
.N2
EF/ cG
 
#t!I
EF/ cK















!I.&'UW&UW5
!"#$%&'()&*
Su%&'84"-4vA2TUW
S&(*%&'5

 
EF/ cX
2

j+2(wN%"2
&4*:"7!<o*>
#$2>x25

j+2(wN%*3
/,4"7!<o*>
#$(!9>x25

Bài giảng : Lý thuyết đồ thị docx

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về