Джумадильдаев А.С. Элементы дискретной математики (часть 1)
Подождите немного. Документ загружается.
•
±u
k
=0.
G v
1
,...,v
n
A =(a
i,j
) D =(d
i,j
)
a
i,j
= v
i
v
j
i = j,
d
i,i
= deg v
i
,
d
i,j
= −a
i,j
, i = j
.
D D
i,j
(i, j)
D =(α
i,j
).
n
j=1
α
i,j
=0,i=1, 2,...,n,
n
i=1
α
i,j
=0,i=1, 2,...,n.
B · 1 =0,
1
t
·B =0,
1 n
det D =0, rank D ≤ n −1. rank D < n −1, D
i,j
=0,
1 ≤ i, j ≤ n.
rank D = n − 1. D
adj
D
adj
=
D
11
D
21
··· D
n1
D
12
D
22
··· D
n2
D
1n
D
2n
··· D
nn
DD
adj
= D
adj
D =(det D)E.
DD
adj
=(det D)E =0.
DD
adj
=0, X D
adj
DX =0. n − 1.
1.
DX =0
1
D
i1
= D
i2
= ···= D
in
,i=1, 2,...,n.
D
1i
= D
2i
= ···= D
ni
,i=1, 2,...,n.
D
adj
D D
i,j
(i, j)
G D
i,j
i, j.
r
@
@
@
@
rr
r
1
2
4
3
D =
3 −2 −10
−24−1 −1
−1 −14−2
0 −1 −23
|D
1,1
| =
4 −1 −1
−14−2
−1 −23
=21
r
↓↓
←
←
rr
r
12
A
B
C
D
pppppppp`
`
`
`
`
`
p
p
p
p
p
p
pppppppp
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
p
@
%
r
3
@
%
r
4
r
5
%
r
1
@
%
@
r
2
− +
@
@
@
@
G
v
1
e
1
v
2
e
2
···v
k−1
e
k−1
v
k
e
i
v
i
v
i+1
e
1
,...,e
k
k v
k
= v
1
. v
k
{e
1
,...,e
k−1
}. v
k
e
k
e
1
,...,e
k−1
e
k
v
k+1
, v
1
,
k. v
k
= v
1
v
1
e
1
v
2
e
2
···v
k−1
e
k−1
v
k
e
k
v
1
.
L = v
1
e
1
v
2
e
2
···v
k−1
e
k−1
v
k
e
k
v
1
e
1
,e
2
,...,e
k
E = {e
1
,...,e
k
}, E
G. F G e
1
,...,e
k
. H
L
G e
H u
L. L
H u
.
H L
H L
H
H
H
H
H
H
@
@
@
@
@
@
@
@
@
@
r
u
LL
A
A
A
AP
P
P
P
P
P
L L
.
k L. L
G
v
1
e
1
v
2
e
2
...v
k−1
e
k−2
v
k
v
1
= v
k
.
v
i
, 1 <i<k,
e
i−1
e
i
.
v
1
e
1
v
k
e
k−1
deg v
k
ABDCBEDAE A
E.
A
B
C
D
E
6@
@
@
@R
6
@
@I
-
-
deg A =3,degB =4,degC =2,degD =4,degE =3.
A E
A
BC
D
E
@
@
@
@
deg A = deg B = deg C = deg C =3,degE=4.
@
@
@
@
@
@
@
@
A C B D
a, b, c, d, e, f g
@
@
@
@
@
@
@
@
A
B
C
D
a
b
c
d
e
f
g
4 > 2
r
r
r
r
H
H
H
H
H
H
H
H
A
B
C
D
g
e
f
ac
bd
deg A =3,degB=5,degC=3,degD=3.
K
2,2
,K
2,3
K
5
K
3,3
.
r
r
r
rr
r
r
r
rr
@
b
b
b
b
b
J
J
J
J
J
C
C
C
C
C
Z
Z
Z
Z
K
5
:
r
r
r"
"
"
b
b
b
C
C
C
C
C
rr
A
A
A
Z
Z
Z
Z
G v e f
e − v + f =2.
k = deg v, v ∈ V.
n
2e
kv =2e.
e = kv/2.
f. n
fn =2e.
f =2e/n = kv/n.
v − kv/2+kv/n =2.
2vn − kvn +2kv =4n,
v(2n − kn +2k)=4n.
v, n ∈ Z,
2n +2k −kn ≥ 0.
(n − 2)(k − 2) < 4.
< 4
1, 2, 3. n, k
n − 2=1,k− 2=1,
n − 2=1,k− 2=2,
n − 2=1,k− 2=3,
n − 2=2,k− 2=1,
n − 2=3,k− 2=1.
k n v e f
3 3 4 6 4
3 4 8 12 6
3 5 20 30 12
4 3 6 12 8
5 3 12 30 20
H
H
H
H
H
H
H
H
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
@
@
@
@
X
X
X
X
X
X
X
X
@
@
@
@
@
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
C
C
C
C
C
C
C
C
C
C
\
\
\
\
X
X
X
X
X
X
X
X
H
H
H
H
H
H
@
@
@
@
@
A
A
A
A
A
A
A
A
A
A
A
A
A
A
A
C
C
C
C
C
C
C
C
C
C
H
H
B
B
B
Q
Q
Q
A
A
A
A
a
a
!
!
J
J
A
A
A
A
A
A
Q
Q
Q
Q
Q
Q
Q
J
J
J
H
HH
H
H
H
@
@
@
@
`
`
`
A
A
A
A
A
A
A
A
A
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q
G =(V,E)
G∗ V ∗
V ∗ G
u, v ∈ V
∗
G
{1, 2,...,n}
n =2 i
1 2
...i
n−2
i
1
,...,i
n−2
∈
{1, 2,...,n}.
T
{1, 2,...,n}
v
i
1
v
i
2
.
v
i
1
v
i
1
v
i
2
. i
2
v
i
2
.
n −2 i
1
i
2
...i
n−2
@
@
@
@
@
@
@
@rr
r
r
rr
−→
@
@
@
@
@
@
@
@r
r
r
rr
−→
@
@
@
@r
r
r
−→
r
@
@
@
@r
r
r
−→
@
@
@
@r
r
r
⇒
i
1
i
2
...i
n−2
{1, 2,...,n}. T i
1
i
2
...i
n−2
i
1
i
2
...i
n−2
12 ...n.
j
1
. i
1
j
1
i
1
j
1
.
i
2
j
2
j
2
{1, 2,...,n}.