Файл: Ху, Т. Целочисленное программирование и потоки в сетях.pdf

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 150

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

490

 

 

 

 

ПРИЛОЖЕНИЕ D

 

 

 

 

 

 

р (G il, (0))

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Грани

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

С т р о к а '''''— ____

7i

72

74

75

77

78

79

7io

 

 

 

1

 

2

1

2

2

2

1

1

1

2

1

3

 

 

 

2

 

1

2

1

1

1

2

2

2

1

2

3

 

 

 

3

 

10

9

8

7

6

5

4

3

2

1

И

 

 

 

4

 

9

7

5

3

1

10

8

6

4

2

И

 

 

 

5

 

8

5

2

10

7

4

1

9

6

3

И

 

 

 

6

 

7

3

10

6

2

9

5

1

8

4

11

 

 

 

7

 

6

1

7

2

8 '

3

9

4 10

5

11

 

 

 

8

 

5

10

4

9

3

8

2

7

1

6

И

 

 

 

9

 

4

8

1

5

9

2

6

10

3

7

И

 

 

 

10

 

3

6

9

1

4

7

10

2

5

8

и

 

 

 

И

 

2

4

6

8

10

1

3

5

7

9

и

 

 

 

12

 

1

2

3

4

5

6

7

8

9

10

11

 

 

 

13

 

18

14

10

6

13

9

16

12

8

4

22

 

 

 

14

 

16

10

4

9

14

8

13

18

12

6

22

 

 

 

15

 

14

6

9

12

4

18

10

13

16

8

22

 

 

 

16

 

13

4

6

8

10

12

14

16

18

9

22

 

 

 

17

 

12

13

14

4

16

6

18

8

9

10

22

 

 

 

18

 

10

9

8

18

6

16

4

14

13

12

22

 

 

 

19

 

9

18

16

14

12

10

8

6

4

13

22

 

 

 

20

 

8

16

13

10

18

4

12

9

6

14

22

 

 

 

21

 

6

12

18

13

8

14

9

4

10

16

22

 

 

 

22

 

4

8

12

16

9

13

6

10

14

18

22

 

Вершины Р (Gii, (0))

 

 

 

 

 

 

 

 

 

 

 

 

1 . ft)

=

(H)

 

30.

(te)

 

= ( 1 1 )

 

 

58.

(tg, f7, tg):=

(1 , 1 , 1 )

2 . (ti, t2)

=

(1.5)

 

31.

i h , h )

=

(4,1)

 

 

59.

(t7, tg)

=

(5, 1)

3.

(t2)

=

(1 1 )

 

32.

(t2, t7)

=

(2 , 1 )

 

 

60. (t5, tg, tg):= (1,1,1)

4.

(t2, t3)

=

(4,1).

 

33.

(ti, t3, f7) =

(1,1,1)

 

61.

(tg, tg)

=

(3,1)

5.

(tx, t3)

=

(2, 3)

 

34.

(t3, t7)

=

(5,1)

 

 

62.

(t4 ,t 9)

=

d ,2 )

6-

(t2>t3)

=

(1,3)

 

35.

(t4, t7)

=

d ,l )

 

 

63.

(ts, tg)

=

(3,2)

7.

(f3)

=

(11)

 

36.

(*5, t7)

=

(3,1)

 

 

64.

(t3, tg)

=

(2,3)

8.

(ij, t4)

=

(3,2)

 

37.

(t3, t6, t7) =

(1,2,1)

 

65.

(tg, tg)

=

(1.3)

9.

(<lt t2, t4) = ( l , l , 2 )

 

38.

(t|, t7)

=

(1.3)

 

 

66.

(tg, tg)

=

(1,4)

10.

(*з, £4)

=

(1,2)

 

39.

(te, t7)

=

(2,3)

 

 

67.

(tg)

=

(11)

11.

4

=

d ,5 )

 

40.

(t5, t7)

=

d ,4 )

 

 

68. (ti, 110)

=

(1,1)

(<2, * )

 

41.

(*7)

 

 

 

69.

(t3, tio)

12.

(t4)

=

(H)

 

 

=

(11)

 

 

=

(4,1)

13.

(f2, t3)

=

(3,1)

 

42.

(ti, f8)

=

(3,1)

 

 

70.

(t4, t4o)

=

(3,1)

14.

(f3, t5)

=

(2 , 1 )

 

43.

(ti,

t2, tg) =

(1 , 1 , 1 )

 

71.

(tg, tio)

= (2 , 1 )

15.

(t2, t4, t5) =

( l , l , l )

 

44.

(t3, tg)

=

(1 , 1 )

 

 

72.

(t5,t7,tig) =

(1 , 1 , 1 )

16.

(t4, tft)

=

d . 2 )

 

45.

(f4, t5, t8) =

(1 , 2 , 1 )

 

73.

(t4, tg, tio) =

(1 , 1 , 1 )

17.

(t4 ,t 5)

=

(3,2)

 

46.

(t5, t8)

=

(5,1)

 

 

74.

(t3,tg,tio) =

(1 , 1 , 1 )

18.

(f2, £5)

=

(1.4)

 

47.

(t7, t8)

=

(2 , 1 )

 

 

75.

(t7, tg, tio) =

(2 , 1 , 1 )

19.

(f5)

=

(1 1 )

 

48.

(f2, ts)

=

(3, 2)

 

 

76.

(t5, tg, tio) =

(1 , 2 , 1 )

2 0 .

(ft, f6)

=

(5, 1)

 

49.

(f2, t4, t8) =

(1 , 1 , 2 )

 

77.

(tg, tio)

=

(5,1)

2 1 .

(flt fa, t6) =

(1 . 2 , 1 )

 

50.

(tg, t8)

=

(1 , 2 )

 

 

78.

(t2 , tio)

= (1 , 2 )

2 2 .

((4, t3, te) =

(2 , 1 , 1 )

 

51.

(ti, t8)

=

d ,4 )

 

 

79.

(15, tg, tio) =

(1 , 1 , 2 )

23.

(t2, t3, te) =

( l , l , l )

 

52.

(t4, t8)

=

(1,5)

 

 

80.

(tg, tio)

=

(3,2)

24.

(t4, t4, t6) =

( l , l , l )

 

53.

(t8)

 

=

(1 1 )

 

 

81.

(t3>*io)

=

d,3)

25.

(t4, tg)

=

(4,1)

 

54.

(t4, tg)

=

(2,1)

 

 

82.

(t7, tio)

=

(2,3)

26.

(f5, t6)

=

(1.1)

 

55.

(f2, tg)

=

(1,1)

 

 

83.

(t4, tio)

=

(1,4)

27.

(t2, t6)

=

(2,3)

 

56.

(tg, tg)

=

(4,1)

 

 

84.

(t5, t10)

=

(1.5)

28.

(t4, t6)

=

(1.3)

 

57.

(t3, t7, tg) =

(2,1,1)

 

85.

(tio)

=

(H)

29.

(t3, te)

=

(1,5)

 

 

 

 

 

 

 

 

 

 

 

 


Матрица инциденций P(G u, (0))

'v -

Грань

 

 

 

 

 

 

8

 

 

 

12

13

14

15

16

17

18

19

20

21

22

23

2 4

25

26

27

28

29

30

31

32

 

1

2

3

4

5

6

7

9

10

11

Вершина

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

2

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

3

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

1

1

1

1

1

1

1

4

0

0

0

0

0

0

1

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

1

0

0

1

1

1

1

1

1

1

5

0

0

0

0

0

0

0

0

1

0

0

1

0

0

0

0

0

0

0

0

0

0

0

1

0

1

1

1

1

1

1

1

6

0

0

0

0

1

0

0

0

1

0

0

1

0

1

0

1

0

0

0

0

0

0

1

0

0

1

1

1

1

1

1

1

7

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

1

1

1

1

1

1

1

8

0

0

0

0

0

0

0

0

0

1

0

1

0

0

0

0

0

0

0

0

0

0

0

1

1

0

1

1

1

1

1

1

9

0

0

0

0

0

0

1

0

0

1

0

1

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

1

1

1

1

1

10

0

1

0

1

0

0

1

0

1

1

0

1

1

1

0

1

1

0

0

0

0

0

1

1

0

0

1

1

1

1

1

1

11

0

0

0

0

0

0

1

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

0

1

1

1

1

1

1

12

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

0

1

1

1

1

1

1

13

0

0

0

0

0

1

1

0

0

0

0

1

0

0

1

1

0

0

0

0

0

0

1

0

1

1

0

1

1

1

1

1

14

0

1

0

1

1

0

0

1

1

0

0

1

0

1

1

1

0

1

0

0

0

0

1

1

0

0

0

1

1

1

1

1

15

0

0

0

1

0

1

1

0

0

1

0

1

0

0

1

1

0

0

0

0

0

0

1

0

1

0

0

1

1

1

1

1

16

0

1

0

1

0

1

0

1

0

1

0

1

0

0

1

0

0

1

0

0

1

1

0

1

1

1

0

1

1

1

1

1

17

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

0

0

1

1

1

1

1

18

0

0

0

1

0

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

1

0

1

1

0

1

1

1

1

1

19

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

0

1

1

1

1

1

20

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

0

1

1

1

1

21

0

0

0

0

0

0

1

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

0

1

1

1

1

22

0

0

0

0

0

0

0

0

1

0

1

1

0

0

0

0

0

0

0

0

0

0

0

1

0

1

1

0

1

1

1

1

23

0

0

0

0

1

0

1

0

1

0

1

1

0

1

0

1

0

0

0

0

0

0

1

0

0

1

1

0

1

1

1

1

24

0

0

0

0

0

0

1

0

1

1

1

1

0

0

0

0

1

0

0

1

0

0

0

1

1

0

1

0

1

1

1

1

25

0

0

0

0

0

0

1

0

0

1

0

0

0

0

0

0

1

0

0

0

0

0

1

1

1

0

1

0

1

1

1

1

26

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

1

1

1

1

27

0

0

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

1

0

1

1

1

0

1

1

1

1

28

0

0

0

0

0

0

1

0

1

0

1

0

0

0

0

0

1

0

0

1

0

0

1

1

1

0

1

0

1

1

1

1

29

0

0

0

0

0

0

0

0

1

0

1

0

0

0

0

0

0

0

0

0

0

0

1

1

0

1

1

0

1

1

1

1


Продолжение

Г р а н ь

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

1

В ер ш и н а

30

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

0

1

1

1

1

31

0

0

0

0

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

1

0

1

0

1

1

1

0

1

1

1

32

1

0

0

0

1

1

1

0

0

0

1

1

0

0

1

1

0

1

0

0

0

1

1

0

1

1

1

1

0

1

1

1

33

0

0

0

0

1

0

0

1

1

0

1

1

0

0

0

0

0

1

0

0

0

1

0

1

1

1

1

1

0

1

1

1

34

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

1

1

1

0

1

1

1

35

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

1

1

0

1

1

1

36

0

0

0

1

0

1

0

1

0

0

0

0

0

0

1

0

0

1

0

0

0

0

1

1

1

1

0

1

0

1

1

1

37

0

0

0

0

1

0

0

0

1

0

1

0

0

0

0

0

0

0

0

0

0

0

1

1

0

1

1

0

0

1

1

1

38

0

0

0

0

1

0

0

1

0

0

1

0

0

0

0

0

0

1

0

0

0

1

0

1

1

1

1

1

0

1

1

1

39

0

0

0

0

1

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

0

0

1

1

1

40

0

0

0

0

1

0

0

1

0

0

0

0

0

0

0

0

0

1

0

0

0

0

1

1

1

1

0

1

0

1

1

1

41

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

0

1

1

1

42

0

0

0

0

0

0

0

0

0

1

1

1

0

0

0

0

0

0

0

0

1

1

0

1

1

1

1

1

1

0

1

1

43

0

0

0

0

0

1

1

0

0

1

1

1

0

0

0

0

0

0

0

0

1

1

0

0

1

1

1

1

1

0

1

1

44

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

1

1

1

1

0

1

1

45

0

0

0

1

0

1

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

0

0

1

1

0

1

1

46

0

0

0

1

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

0

1

1

0

1

1

47

1

0

1

0

1

1

0

1

0

0

1

0

0

0

0

0

0

1

1

0

1

1

1

1

1

1

1

1

0

0

1

1

48

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

1

1

1

1

0

1

1

49

0

0

0

0

0

1

1

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

1

0

1

0

1

1

1

0

1

1

50

1

0

1

0

0

1

1

0

0

1

1

0

0

0

0

0

1

0

1

1

1

0

1

1

1

1

1

0

1

0

1

1

51

0

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

0

0

0

0

1

0

0

1

1

1

1

1

1

0

1

1

52

0

0

0

0

0

1

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

0

1

1

1

0

1

1

53

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

0

1

1

54

0

1

0

0

0

0

0

1

1

1

1

1

0

0

0

0

0

0

1

1

1

1

0

1

1

1

1

1

1

1

0

1

55

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

1

1

1

1

1

1

0

1

56

0

0

0

0

0

0

0

0

1

0

1

0

0

0

0

0

0

0

0

1

0

0

1

1

1

1

1

0

1

1

0

1

57

0

0

0

0

1

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

1

1

1

0

1

0

1



Продолжение

>«.

Г р а н ь

1

2

3

4

5

6

7

8

9

10

и

12

13

14

15

16

17

18 19 20

21

22

23 24 25 26 27 28 29 30 31

32

 

 

В ерш ина

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

58

 

0

0

1

0

1

0

0

1

1

0

1

0

0

0

0

0

0

0

1

1

0

0

1

1

1

1

1

0

0

1

0

1

59

 

0

0

0

0

1

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

0

1

0

1

60

 

0

0

1

1

0

1

0

1

0

1

0

0

0

0

0

0

0

0

1

0

1

0

1

1

1

1

0

1

1

0

0

1

61

 

0

0

1

0

0

1

0

0

0

1

0

0

0

0

0

0

0

0

1

0

1

0

1

1

1

1

1

1

1

0

0

1

62

 

0

1

1

1

0

0

0

1

1

1

0

0

1

0

0

0

1

0

1

1

0

0

1

1

1

0

1

1

1

1

0

1

63

 

0

0

0

1

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

0

1

1

1

0

1

64

 

0

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

1

1

1

1

1

0

1

65

 

0

0

1

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

1

1

0

0

1

1

1

1

1

0

1

1

0

1

66

 

0

0

1

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

1

0

0

0

1

1

1

1

1

1

1

0

0

1

67

 

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

1

68

 

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

1

1

1

1

1

1

1

1

0

69

 

0

0

0

0

1

0

0

0

1

0

0

0

0

1

0

0

0

0

0

0

0

0

1

1

0

1

1

1

1

1

1

0

70

 

0

0

0

1

0

0

1

0

0

1

0

0

1

0

0

0

1

0

0

0

0

0

1

1

1

0

1

1

1

1

1

0

71

 

1

0

1

0

1

0

1

0

1

0

1

0

1

1

0

0

1

0

0

1

0

0

1

1

1

1

1

0

1

1

1

0

72

 

0

0

1

1

1

1

0

1

0

0

0

0

0

0

1

0

0

1

0

0

0

0

1

1

1

1

0

1

0

1

1

0

73

 

0

0

1

1

0

1

1

0

0

1

0

0

1

0

0

0

1

0

0

0

0

0

1

1

1

0

1

1

1

0

1

0

74

 

0

0

1

1

1

0

0

1

1

0

0

0

1

1

0

0

0

0

0

0

0

0

1

1

0

1

1

1

1

1

0

0

75

 

0

0

1

0

1

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

0

1

0

0

76

 

0

0

1

1

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

0

1

1

1

0

0

77

 

0

0

1

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

0

78

 

1

0

1

1

1

1

1

0

0

0

0

0

1

1

1

1

0

0

0

0

0

0

1

0

1

1

1

1

1

1

1

0

79

 

0

0

1

1

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

0

1

1

0

1

0

80

 

0

0

1

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

0

1

0

81

 

0

0

1

1

1

0

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

0

1

1

0

1

1

1

1

1

1

0

82

 

0

0

1

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

0

1

1

0

83

 

0

0

1

1

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

1

1

1

0

1

1

1

1

1

0

84

 

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

0

1

1

1

1

0

85

 

0

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

1

0