Вход

Дискретная математика: "Графы"

Курсовая работа по математике
Дата добавления: 22 декабря 1998
Язык курсовой: Русский
Word, rtf, 2 Мб (архив zip, 274 кб)
Курсовую можно скачать бесплатно
Скачать
Данная работа не подходит - план Б:
Создаете заказ
Выбираете исполнителя
Готовый результат
Исполнители предлагают свои условия
Автор работает
Заказать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу






Gор(V,X)


???. 1


??????1 ??? ?????????????????? ????? G, ???????????????? ? ?????? Gор ???????? (????????????? ???????) :

?) ????????? ?????? V ? ????????? ????? X, G(V,X);

?) ?????? ?????????;

?) ??????? ?????????????;

?) ??????? ?????.

?) ??? ????? Gор ???????? ??????? ?????????.


????????? ?????? - ??. ??? 1

?) V={0,1,2,3,4,5,6,7,8,9}

X={{0,1},{0,2},{0,3},{1,2},{1,4},{1,5},{1,6},{1,7},{2,3},{2,5},{3,8},{3,9},{4,5},{4,6},{5,3},{5,6},{5,8},{6,9},{7,8},{7,9},{8,9}}

? ?????????? ????? ????? ???????????? ???????? ? ????????? ??????? ??????? ? ????.


?) ?0={1,2,3};

?1={0,2,4,5,6,7};

?2={0,1,3,5};

?3={0,2,5,8,9};

?4={1,5,6};

?5={1,2,3,4,6,8};

?6={1,4,5,9};

?7={1,8,9};

?8={1,3,5,7,9};

?9={3,6,7,8};



?) ????????? ?????? ? ????? ?????????????? ?. ?)


0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

0

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

1

0

0

1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

0

0

0

2

0

1

0

1

0

0

0

0

1

1

0

0

0

0

0

0

0

0

0

0

0

3

0

0

1

0

0

0

0

0

1

0

1

1

0

0

1

0

0

0

0

0

0

4

0

0

0

0

1

0

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

5

0

0

0

0

0

1

0

0

0

1

0

0

1

0

1

1

1

0

0

0

0

6

0

0

0

0

0

0

1

0

0

0

0

0

0

1

0

1

0

1

0

0

0

7

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

1

1

0

8

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

1

0

1

0

1

9

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

1

0

1

1


?) ???????? ??????? ???????? ???????, ?.?. ??????? ????? ?????????????????? ????? ??????????? ???????????? ??????? ?????????.


0

1

2

3

4

5

6

7

8

9

0



8

3

5













1




1



2

2

4

5





2





2



5









3








1





1

6

4







4

2







5








2



1



6













2

7










1

1

8











6

9













?) ??????? ????????? ??? ????? Gор.


0

1

2

3

4

5

6

7

8

9

0



1

1

1













1

-1



1



1

1

1

1





2

-1

-1



1



1









3

-1



-1





-1





1

1

4



-1







1

1







5



-1

-1

1

-1



1



1



6



-1





-1

-1







1

7



-1













1

1

8







-1



-1



-1



1

9







-1





-1

-1

-1






?????? 2 ????? ??????? D(G), ?????? R(G), ?????????? ??????? Z(G) ??? ????? G ; ??????? ???????, ?????????? ???????? ????? G.


D(G)=2

R(G)=2

Z(G)=10

??? ??????? ????? G(V,X) ???????? ????????.



?????? 3 ?????????????? ??????? ????? G, ????????? ?????????:

?) "?????? ? ???????";

?) "?????? ? ??????".

???????? ??????? - .

?)

?)


?????? 4 ????????? ???????? ????? ????? ????? ???????????? ???? ????? G. ???????? ??? ??????? ?? ????????? ?????????? ??????, ?????? ?? ???????? ??????? .



??? ?????????? ?????? - 14.


??? ??????? ??????: 000011000001111111.


?????? 5 ????????? ???????? ???????? ????? ????? ?????????? ????? ?? ???????  ????? G.



??? ?????????? ???? - 8.


?????? 6 ????????? ???????? ????? - ??????????, ????? ???????????? ????? ?? ?????????? ??????????? ??????????????? ???? {Gор ,  , w}. ??????? ?????? ???????????? ????.


?????????????????? ????????? ???? (?????????? ????? ???????? ??????????):

1-? ???


2-? ???


3-? ???


4-? ???


5-? ???


6-? ???


7-? ???

???????????? ?????:


??? ????? ?? ???????, ????? {6,9},{7,9},{3,9}, ???????? ??????? , ?????????, ? ?????????? ????? {8,9}, ?????????? ?? ??????? 8, ?? ????? ???????? ??????? ???????? ??????? ???????, ??? ??? ????????? ??? ?????, ???????? ??????? 8. ??????? ??????? - ???? ????????? ??? ?????????? ?????, ?? ???????  ???????????, ??? ???????? ????????? ????????????? ?????? ? ????.

???????????? ????? ? ???? ????? 12.

??????????? ?????? ???? ?? ????? ?????: {{0,1},{0,2},{0,3}}. ??? ?????????? ??????????? ????? 16

??????????? ?????? ???? ?? ?????????? ???????????: {{6,9}, {7,9}, {3,9}, {3,8}, {5,8}, {7,8}}. ??? ?????????? ??????????? ????? 12.


?????? 7 (?????? ? ??????????) ???????? ????????? ?????????????????? ?????? ????? G.

?) ??????? ? ????? G ???????? ????. ???? ??????? ???? ?? ??????????, ?? ? ????? G ???????? ?????????? ????? ????? ????? ???????, ????? ? ????? ????? ????? ???? ??????? ???????? ????.

?) ??????? ? ????? G ??????? ????. ???? ?????? ????? ?? ??????????, ?? ? ????? G ???????? ?????????? ????? ????? ????? ???????, ????? ? ????? ????? ????? ???? ??????? ??????? ????.


????????? ?????????????????? ?????? ????? G:

(3,6,4,5,3,6,4,3,4,4)

?) ??? ????????????? ????????? ???? ????????? ?????? ??? ??????? ? ????????? ?????????, ??????? ?????????? ???????? ???? ?????, ?????? ????? ????????? 4 ? 7.

?????????? ???????? ????: 0,3,2,0,1,2,5,1,4,5,6,1,7,4,6,9,7,8,9,3,8,5,3.

????? ????????? ???? (??????????? ????? ???????? ?????????):



?) ?????????? ?????? ?) ????????? ????? {3,0}, ??????? ???????? ???? (??? ???? ???????? ??????? ????????????? ???????? ????? - ???????? ???????? ???? ??????). ????? {3,0} ???????, ??? ?? ???????????? ???????, ?? ??? ????????????? ????? ?????? ????? {0,7} ? {4,3} ?????? ????? ?????????.

?????????? ??????? ????: 0,3,2,0,1,2,5,1,4,5,6,1,7,4,6,9,7,8,9,3,8,5,3,0.

????? ???????? ????? (??????????? ????? ???????? ?????????):




?????? 8

?) ??????? ? ????? Gор ??????????? ????. ???? ????? ???? ?? ??????????, ?? ? ????? Gор ???????? ?????????? ??????????? ????? ????? ????? ???????, ????? ? ????? ????? ??????????? ???? ????? ???? ???????.

?) ??????? ? ????? Gор ??????????? ????. ???? ????? ???? ?? ??????????, ?? ? ????? Gор ???????? ?????????? ??????????? ????? ????? ????? ???????, ????? ? ????? ????? ??????????? ???? ????? ???? ???????.



?) ??????????? ???? (????? ? ?????????? ??????????? ???????? ?????????):



?) ??????????? ???? (????? ? ?????????? ??????????? ???????? ?????????):



?????? 9 (?????? ? ????????????) ??? ?????? ??????????????? ?????????????? ???? ? ????????? x1, x2,...xn.??? ???? xixj ????? ?????????? Vij ??????? ?????. ????????? ???????? ?????? ?????? ? ??????, ????? ??????????? ?????? ???????????? (?????????????) ????. ?????? ?? ???????????? ???????? ???????????? ??????? ?????? ? ?????? ?? ??????????? ????????, ?????????? ??????? ? ?????????? ,??? . ????????? ???????.


???????? ???????.


x1

x2

x3

x4

x5

x6


x1



3

7

2



11


x2

8



06



4

3


x3

6

05



7



2


x4

6



13



5




x5

3

3

3

4



5


x6

8

6



2

2













??????? ? 14


x1

x2

x3

x4

x5

x6


x1



1

5

01



7

2

x2

8



01



4

1


x3

6

00



7



00


x4

1



8



01



5

x5

01

00

00

1



00

3

x6

6

4



00

00



2







2



?????? ?? ???????? x2-x3:

??????? 23 =14+0=14


x1

x2

x4

x5

x6


x1



1

01



7


x3

6



7



06


x4

1





01




x5

01

01

1



00


x6

6

4

00

00













??????? 23 =14+1=15


x1

x2

x3

x4

x5

x6


x1



1

5

01



7


x2

7







3

03

1

x3

6

00



7



00


x4

1



8



01




x5

01

00

05

1



00


x6

6

4



00

00












?????????? ?? 23. ?????? ?? ???????? x3-x6:

??????? 23E36 =14+0=14


x1

x2

x4

x5


x1



1

01




x4

1





01


x5

01

01

1




x6

6



00

00








??????? 2336 =14+6=20


x1

x2

x4

x5

x6


x1



1

01



7


x3

01



1





6

x4

1





01




x5

00

01

1



07


x6

6

4

00

00












?????????? ?? 2336. ?????? ?? ???????? x4-x5:

??????? 23E3645 =14+0=14


x1

x2

x4


x1



1

01


x5

01

01

1


x6

6



00








??????? 233645 =14+1=15


x1

x2

x4

x5


x1



1

01




x4

00







1

x5

01

01

1




x6

6



00

00









?????????? ?? 233645. ?????? ?? ???????? x5-x1:

??????? 23364551 =14+1=15


x2

x4


x1

1



1

x6



00







??????? 23364551 =14+6=20


x1

x2

x4


x1



1

01


x5



01




x6

0



00



6






???????????? ????? ??????????? ??????: 2,3,6,4,5,1,2.


????????? ?????????:




?????? 10 (?????? ? ???????????) ??? ?????? ?????????? ???? Knn ? ????????? ?????? ???? x1, x2,...xn.? ????????? ?????? ???? y1, y2,...yn..??? ????? {xi,yj} ???????? ?????????? vij ??????? ?????. ????????? ?????????? ????????, ????? ??????????? ????????????? ???????????? (????????????? ????). ????????? ???????.


??????? ????? ??????????? ????? K55 :


y1

y2

y3

y4

y5

x1

2

0

0

0

0

x2

0

7

9

8

6

x3

0

1

3

2

2

x4

0

8

7

6

4

x5

0

7

6

8

3




?????? ???? - ????????? ????? ?? ?????, ?. ?. ???? ??? ???? ?? ???? ????? ? ????????.

?????? ???? - ?????????? ??????? ?????????????.


y1

y2

y3

y4

y5

x1

2

0

0

0

0

x2

0

7

9

8

6

x3

0

1

3

2

2

x4

0

8

7

6

4

x5

0

7

6

8

3


?????? ???? - ?????????? ????????????? ?????????????.



y1

y2

y3

y4

y5


x1

2

0

0

0

0

X

x2

0

7

9

8

6

X

x3

0

1

3

2

2


x4

0

8

7

6

4


x5

0

7

6

8

3



X

X






????????? ???? - ?????????? ??????????? ?????.


y1

y2

y3

y4

y5


x1

2

0

0

0

0


x2

0

7

9

8

6

5

x3

0

1

3

2

2

1

x4

0

8

7

6

4

2

x5

0

7

6

8

3

3


4








????? ???? - ????????? ???????????? ????????? ?????.


y1

y2

y3

y4

y5


x1

3

0

0

0

0


x2

0

6

8

7

5

5

x3

0

0

2

1

1

1

x4

0

7

6

5

3

2

x5

0

6

5

7

2

3


4






??????? ? ????????? ?????????. ??????? ?? ??????? ?????.

?????? ?????????????:


y1

y2

y3

y4

y5


x1

3

0

0

0

0


x2

0

6

8

7

5


x3

0

0

2

1

1


x4

0

7

6

5

3


x5

0

6

5

7

2









???????????? ?????????????:


y1

y2

y3

y4

y5


x1

3

0

0

0

0

X

x2

0

6

8

7

5

X

x3

0

0

2

1

1


x4

0

7

6

5

3


x5

0

6

5

7

2



X

X






??????????? ?????:


y1

y2

y3

y4

y5


x1

3

0

0

0

0

6

x2

0

6

8

7

5

7

x3

0

0

2

1

1

1

x4

0

7

6

5

3

2

x5

0

6

5

7

2

3


4

5






???????????? ?????:


y1

y2

y3

y4

y5


x1

3

0

0

0

0

6

x2

0

6

8

7

5

7

x3

0

0

2

1

1

1

x4

0

7

6

5

3

2

x5

0

6

5

7

2

3


4

5







?????? ?????????????:


y1

y2

y3

y4

y5


x1

3

0

0

0

0

6

x2

0

6

8

7

5

7

x3

0

0

2

1

1

1

x4

0

7

6

5

3

2

x5

0

6

5

7

2

3


4

5






???????????? ?????????????:


y1

y2

y3

y4

y5


x1

3

0

0

0

0

X

x2

0

6

8

7

5


x3

0

0

2

1

1

X

x4

0

7

6

5

3

X

x5

0

6

5

7

2



X

X

X





??????????? ?????:


y1

y2

y3

y4

y5


x1

3

0

0

0

0


x2

0

6

8

7

5

1

x3

0

0

2

1

1


x4

0

7

6

5

3


x5

0

6

5

7

2

2


3







???????????? ?????:


y1

y2

y3

y4

y5


x1

5

0

0

0

0


x2

0

4

6

5

3

1

x3

2

0

2

1

1


x4

2

7

6

5

3


x5

0

4

3

5

0

2


3







?????? ?????????????:


y1

y2

y3

y4

y5


x1

5

0

0

0

0


x2

0

4

6

5

3


x3

2

0

2

1

1


x4

2

7

6

5

3


x5

0

4

3

5

0










???????????? ?????????????:


y1

y2

y3

y4

y5


x1

5

0

0

0

0

X

x2

0

4

6

5

3

X

x3

2

0

2

1

1

X

x4

2

7

6

5

3


x5

0

4

3

5

0

X


X

X

X


X



??????????? ?????:


y1

y2

y3

y4

y5


x1

5

0

0

0

0


x2

0

4

6

5

3


x3

2

0

2

1

1


x4

2

7

6

5

3

1

x5

0

4

3

5

0










???????????? ?????:


y1

y2

y3

y4

y5


x1

5

0

0

0

0


x2

0

4

6

5

3


x3

2

0

2

1

1


x4

0

5

4

3

1

1

x5

0

4

3

5

0










?????? ?????????????:


y1

y2

y3

y4

y5


x1

5

0

0

0

0


x2

0

4

6

5

3


x3

2

0

2

1

1


x4

0

5

4

3

1

1

x5

0

4

3

5

0










???????????? ?????????????:


y1

y2

y3

y4

y5


x1

5

0

0

0

0

X

x2

0

4

6

5

3

X

x3

2

0

2

1

1

X

x4

0

5

4

3

1


x5

0

4

3

5

0

X


X

X

X


X




??????????? ?????:


y1

y2

y3

y4

y5


x1

5

0

0

0

0


x2

0

4

6

5

3

3

x3

2

0

2

1

1


x4

0

5

4

3

1

1

x5

0

4

3

5

0



2







???????????? ?????:


y1

y2

y3

y4

y5


x1

6

0

0

0

0


x2

0

3

5

4

2

3

x3

3

0

2

1

1


x4

0

4

3

2

0

1

x5

1

4

3

5

0



2







?????? ?????????????:


y1

y2

y3

y4

y5


x1

6

0

0

0

0


x2

0

3

5

4

2

3

x3

3

0

2

1

1


x4

0

4

3

2

0

1

x5

1

4

3

5

0



2







???????????? ?????????????:


y1

y2

y3

y4

y5


x1

6

0

0

0

0

X

x2

0

3

5

4

2

X

x3

3

0

2

1

1

X

x4

0

4

3

2

0


x5

1

4

3

5

0

X


X

X

X


X



??????????? ?????:


y1

y2

y3

y4

y5


x1

6

0

0

0

0


x2

0

3

5

4

2

4

x3

3

0

2

1

1


x4

0

4

3

2

0

1

x5

1

4

3

5

0

5


2




3




? ?????????? ?????:


y1

y2

y3

y4

y5


x1

6

0

0

0

0


x2

0

1

3

2

2

4

x3

3

0

2

1

1


x4

0

2

1

0

0

1

x5

1

4

3

5

0

5


2




3


???????? ????



?????????? ????:

??? ?????????? ???????????? ????????????? = 12.


?????? 11 ?????? ?????? 10, ????????? ???????? ?????? ? ?????? (??????????? ??????? xi ? yj).


??????? ? (????????). ?????? - xi , ??????? - yj. =0


1

2

3

4

5


1

2

01

03

02

02


2

06

7

9

8

6


3

01

1

3

2

2


4

04

8

7

6

4


5

03

7

6

8

3










?????? ?? ???????? x2 - y1:

??????? ?21 =0+8=8


2

3

4

5


1

00

02

01

00


3

01

2

1

1

1

4

4

3

2

02

4

5

4

3

5

03

3







??????? 21 =0+6=6


1

2

3

4

5


1

2

01

03

02

00


2



1

3

2

01

6

3

01

1

3

2

2


4

04

8

7

6

4


5

03

7

6

8

3









?????????? ?? 21:

?????? ?? ???????? x4 - y1:

??????? 21?41 =6+4=10


2

3

4

5


1

00

02

01

00


2

1

3

2

01


3

01

2

1

1

1

5

4

3

5

03

3







??????? 2141 =6+4=10


1

2

3

4

5


1

2

01

03

02

00


2



1

3

2

01


3

01

1

3

2

2


4



4

3

2

02

4

5

03

7

6

8

3











?????????? ?? ?21:

?????? ?? ???????? x5 - y5:

??????? ?21?55 =8+2=10


2

3

4


1

00

01

00


3

01

2

1


4

2

1

01

2






??????? ?2155 =8+3=11


2

3

4

5


1

00

02

01

00


3

01

2

1

1


4

4

3

2

02


5

1

01

2



3







?????????? ?? ?21?55:

?????? ?? ???????? x3 - y2:

??????? ?21?55?32 =10+0=10


3

4


1

01

00


4

1

01






????? ??????? ????????: x1 - y3 ? x4 - y4. ??? ?? ???????? ??????.

? ????? ????? ??????????? ????????????? ? ??????????? ?????:


????????? ?????????:

© Рефератбанк, 2002 - 2017