b) . .
5 .
:
C | |||||||
¥ | ¥ | ¥ | ¥ | ||||
¥ | ¥ | ||||||
¥ | ¥ | ||||||
¥ | ¥ | ||||||
¥ | ¥ | ||||||
¥ | ¥ | ||||||
¥ | ¥ |
1) l(5)=0; (1)=¥; (2)=¥; (3)=¥;
(4)=¥; (6)=¥; (7)=¥; p=5.
2) l(5)=0;
(1)=min( (1), l(5)+c(5,1))=min(¥, 0+¥)=¥;
(2)=min( (2), l(5)+c(5,2))=min(¥, 0+9)=9;
(3)=min( (3), l(5)+c(5,3))=min(¥, 0+12)=12;
(4)=min( (4), l(5)+c(5,4))=min(¥, 0+¥)=¥;
(6)=min( (6), l(5)+c(5,6))=min(¥, 0+2)= 2;
(7)=min( (7), l(5)+c(5,7))=min(¥, 0+20)=20;
p=6.
3) l(6)=2; (1)=¥; (2)=9; (3)=12;
(4)=¥; (7)=20;
(1)=min( (1), l(6)+c(6,1))=min(¥, 2+¥)=¥;
(2)=min( (2), l(6)+c(6,2))=min(9, 2+¥)= 9;
(3)=min( (3), l(6)+c(6,3))=min(12, 2+14)=12;
(4)=min( (4), l(6)+c(6,4))=min(¥, 2+9)=11;
(7)=min( (7), l(6)+c(6,7))=min(20, 2+18)=20;
p=2.
4) l(2)=9; (1)=¥; (3)=12; (4)=11;
(7)=20;
(1)=min( (1), l(2)+c(2,1))=min(¥, 9+10)=19;
(3)=min( (3), l(2)+c(2,3))=min(12, 9+21)=12;
(4)=min( (4), l(2)+c(2,4))=min(11, 9+16)= 11;
(7)=min( (7), l(2)+c(2,7))=min(20, 9+¥)=20;
p=4.
5) l(4)=11; (1)=19; (3)=12; (7)=20;
(1)=min( (1), l(4)+c(4,1))=min(19, 11+26)=19;
(3)=min( (3), l(4)+c(4,3))=min(12, 11+¥)= 12;
(7)=min( (7), l(4)+c(4,7))=min(20, 11+27)=20;
p=3.
6) l(3)=12; (1)=19; (7)=20;
(1)=min( (1), l(3)+c(3,1))=min(19, 12+¥)=19;
(7)=min( (7), l(3)+c(3,7))=min(20, 12+32)=20;
p=1.
7) l(1)=19; (7)=min( (7), l(1)+c(1,7))=min(20, 19+¥)=20; p=7.
, :
M5,1={5,2,1}=19;
M5,2={5,2}=9;
M5,3={5,3}=12;
M5,4={5,6,4}=11;
M5,6={5,6}=2;
M5,7={5,7}={5,6,7}=20.
.
k=0
k=1
k=2
k=3
k=4
5) k=5
6) k=6
7) k=7
, :
M1,2={1,2}; M1,3={1,2,3}; M1,4={1,4};
M1,5={1,2,5}; M1,6={1,2,5,6}; M1,7={1,2,5,7};
M2,3={2,3}; M2,4={2,4}; M2,5={2,5};
M2,6={2,5,6}; M2,7={2,5,7}; M3,4={3,6,4};
M3,5={3,5}; M3,6={3,6}; M3,7={3,7};
M4,5={4,6,5}; M4,6={4,6}; M4,7={4,7};
|
|
M5,6={5,6}; M5,7={5,7}; M6,7={6,7};
: , .
3
1: .
: , .
1. GV, G1:GV(5,{2,3}) G2: GV(13,{6,7}). G2 Y.
G1, GV(5,{2,3}).
S=<>;
S=< ,,,,, ,,,,>;
n(Si)={32,22,1,6,13}.
Y1 | |||||
A1 | |||||
2 , (2,3) .
G1, .
G1=(V1,E1): V1={1,2,3,4,5} ;
E1={(1,2),(1,4),(2,4),(2,5),(3,5)} .
G1.
G2, GV(13,{6,7}).
S=<>;
S=< ,,,,,,,,, >;
n(Si)={32,22,1,6,13,15,33,12,16,3,29,18,14}.
Y2 | |||||||||||||
|
|
A2 | |||||||||||||
G2, .
G2=(V2,E2):
V2={1,2,3,4,5,6,7,8,9,10,11,12,13} ;
E2={(1,12),(1,13),(2,3),(2,6),(2,9),(2,11),(3,5),(3,6),(3,11),(4,5),
(4,8),(4,12),(6,7),(6,10),(6,11),(7,8),(7,10),(8,12)} .
G2.
2. G1 .
M | |||||
-1 | -1 | ||||
-1 | -1 | -1 | |||
-1 | |||||
-1 | -1 | ||||
-1 | -1 |
k G .
, G1 3 :
3. G2 .
G2.
:
1)
:
- 1
- 2
- 3
- 4
- 5
G2 , ( Y).
G . Op . . , p-1.
2 | |||||||||||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ||||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ||||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | |||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | |||||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | |||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | |||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | |||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | |||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | |||||
¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ | ¥ |
(2,9)1, (4,8)2, (8,12)3 | |
(2,6)4, (2,11)5, (4,5)6 | |
(3,5)7, (4,12), (6,10)8 | |
(1,12)9, (3,6)10, (6,11) | |
(1,13)11, (6,7)12 | |
(2,3), (7,8) | |
(3,11) | |
(7,10) |
:
|
|
(4,12);
(6,11);
(2,3);
(7,8);
(3,11);
(7,10).
, , .
(2,9)1, (4,8)8, (8,12)9 | |
(2,6)2, (2,11)3, (4,5)7 | |
(3,5)6, (4,12), (6,10)4 | |
(1,12)10, (3,6)5, (6,11) | |
(1,13)11, (6,7)12 | |
(2,3), (7,8) | |
(3,11) | |
(7,10) |
:
(4,12);
(6,11);
(2,3);
(7,8);
(3,11);
(7,10).
4. 4 7.
4- :
7- :
2 : .
1) :
2) :
: , .
2: .
: , .
1. GV, G1:GV(5,{2,3}) G2: GV(13,{6,7}).
G1, GV(5,{2,3}).
S=<>;
S=< ,,,,, ,,,,>;
n(Si)={32,22,1,6,13}.
Y1 | |||||
A1 | deg(vi) | |||||
|
|
G1, .
G1=(V1,E1): V1={1,2,3,4,5} ;
E1={(1,2),(1,4),(2,3),(2,4),(2,5),(3,5)} .
G1.
G1,
G2, GV(13,{6,7}).
S=<>;
S=< ,,,,,,,,, >;
n(Si)={32,22,1,6,13,15,33,12,16,3,29,18,14}.
Y2 | |||||||||||||
A2 | deg(vi) | |||||||||||||
G2, .
G2=(V2,E2):
V2={1,2,3,4,5,6,7,8,9,10,11,12,13} ;
E2={(1,12),(1,13),(2,3),(2,6),(2,9),(2,11),(3,5),(3,6),(3,11),(4,5),
(4,8),(4,12),(6,7),(6,10),(6,11),(7,8),(7,10),(8,12)} .
G2.
G1 . , ( ) .
| V | = p = 5, | E | = q = 6, k =1.
ν=q-p+k=6-5+1=2 ();
|
|
ν*=p-k=5-1=4 ().
G1:
C1={1,2,4,1};
C2={2,5,3,2};
C3={2,1,4,2,5,3,2}.
G1 q.
: z=(z1,z2,z3,,zq):
z1=(1,1,0,1,0,0);
z2=(0,0,1,0,1,1);
z3=(1,1,1,1,1,1).
G1 C3.
3 1 2:
3=1Å2=(1,1,0,1,0,0)Å(0,0,1,0,1,1)=(1,1,1,1,1,1).
:
(1,2) | (1,4) | (2,3) | (2,4) | (2,5) | (3,5) | |
C1 | ||||||
C2 | ||||||
C3 |
3. , G1 G2 , , . , , .
1) G1: , , G1 , .
. , .
V | (1,2) | (1,4) | (2,3) | (2,4) | (2,5) | (3,5) |
:
1={2,1,4,2,3,5,2};
C2={2,5,3,2,1,4,2}.
. (2,3), 2 3 , , G1 .
:
P1={2,1,4,2,5,3};
P2={3,5,2,4,1,2}.
2) G2: 4, 6, 7, 8, 10, 11, 12, 13 , G2 , , .
(6,9), (6,12),.(6,8), (4,7), (11,13). , . , .
.
V | (1,12) | (1,13) | (2,3) | (2,6) | (2,9) | (2,11) | (3,5) | (3,6) |
V | (3,11) | (4,5) | (4,7) | (4,8) | (4,12) | (6,7) | (6,8) | (6,9) |
V | (6,11) | (6,12) | (7,8) | (7,10) | (8,12) | (11,13) | (6,10) | |
:
={2,9,6,11,2,3,11,13,1,12,4,5,3,6,12,8,4,7,6,10,7,8,6,2}.
. (1,6), (3,2), 7 13 , , G2 .
:
P2={13,1,12,11,2,9,7,8,12,4,3,11,6,7,10,6,8,4,6,2,3,6}.
, G2 , , -. , , .
G2 , 2 : 9, 13, , , , .
(9,13), :
Cg = {9,2,3,11,6,10,7,8,4,5,12,1,13,9}.
, - .