Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


Упражнения. 9.1. Найти центр, радиус и диаметр деревьев:




9.1. Найти центр, радиус и диаметр деревьев:

a) б)

 

       
   
 
 


в) г)

 

 

9.2. С помощью леса представить перестановки из n элементов множества M={a,b,c,d} и подсчитать их число.

9.3. На рисунке изображена схема местности. Передвигаться из пункта в пункт можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из этих путей наименьшая длина? У какого – наибольшая длина?

1 2 3

 

 

 


4 5 6

 

7 8 9

9.4. В игре, представленной деревом, первым делает ход игрок A. В какую из четырёх позиций должен пойти игрок A, чтобы выиграть?

 

 
 


1 4

2 3

 

A B B A

 

B A B A B B B A А

 

9.5. По кодовому дереву восстановить двоичный код алфавита {a, b, c, d, e, f, g}.

0 0 a

b

0 1

1 c

0 1 1

d

 

1 0 e

 

f

1 0 0

g

 

9.6. Построить кодовое дерево для кодов:

а) a=0000 б) а=00

b=0101 b=0001

c=0011 c=011

d=01 d=1100

e=100 e=1101

f=101 f=111

g=111

9.7. Дан граф:

v1 1 9 v3

 

1 4 1 6

2 8

5

3 7 6

С помощью дерева найти кратчайший путь из V1 в V7 и его длину.

9.8. Движение из пункта A1 в пункт A9 разрешается только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Определить число возможных путей из пункта A1 в пункт A9 и длину наикратчайшего из них.

A2 A7


A5
4 5 7 9

A9
10 13

A1 13 1

 

A6
5 10 4 8

A4 A

9.9. Построить остов графа. Найти цикломатическое число.

а) б)

 

9.10. Найти остов минимального веса нагруженного графа:

а) б)

1 1

10 8 7

 

4 1 2 3 2 1

9 1 3 3 3 3

2 7

6 2 1

2 2 1

5 1

 

9.11. Построить остов графа. Найти цикломатическое число. Выделить базис циклов графа. Выразить какой-либо цикл в графе через базисные циклы. Составить матрицу базисных циклов.

 

а) б)

 

в)

 

§ 10. Раскраска графов. Планарные графы


Поделиться:

Дата добавления: 2015-01-29; просмотров: 124; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты