Задания

Сдать 8.05.17 до 10:30,  ауд 1439.

Вариант1

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Описать n-вершинный граф, если эксцентриситеты всех его вершин равны 1.

_________________________________________________________________

Вариант 2

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Построить граф с радиусом 3 и диаметром 7.

_______________________________________________________________________

Вариант 3

1) Построить связные  графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Построить граф с радиусом 4 и диаметром 7.

Вариант 4

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Описать n-вершинный граф, который остается связным после удаления любого ребра.

_________________________________________________________________

Вариант 5

1) Построить связные  графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Описать n-вершинный граф, который остается связным после удаления двух любых ребер.

______________________________________________________________________

Вариант 6

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Описать n-вершинный граф, который остается связным после удаления любой вершины.

_____________________________________________________________________

Вариант 7

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Описать n-вершинные однородные графы, степени 1.

_________________________________________________________________

Вариант 8

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Построить граф с радиусом 3 и диаметром 8.

_______________________________________________________________________

Вариант 9

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Построить граф с радиусом 5 и диаметром 8.

______________________________________________________________________

Вариант 10

1) Построить мграфы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Описать n-вершинный граф, диаметр которого равен радиусу.

______________________________________________________________________

Вариант 11

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Описать n-вершинный граф с двумя центральными вершинами.

_______________________________________________________________________

Вариант 12

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Сколько ребер содержит однородный - вершинный граф степени ?

_______________________________________________________________________

Вариант13

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Описать кубические n-вершинные графы. _________________________________________________________________

Вариант 14

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Изобразите куб так, чтобы его ребра не пересекались.

_______________________________________________________________________

Вариант 15

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Построить граф с радиусом 7 и диаметром 9.

Вариант 16

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Опишите построение n-вершинного графа, у которого центр состоит из k вершин.

_________________________________________________________________

Вариант 17

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Докажите, что самодополнительный граф является связным.

_______________________________________________________________________

Вариант 18

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Построить граф с радиусом 5 и диаметром 9.

Вариант 19

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Описать n - вершинный граф, у которого ровно две центральные вершины.

_________________________________________________________________

Вариант 20

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3)Описать n - вершинный граф, у которого одна центральная вершина.

__________________________________________________________________

Вариант 21

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Построить граф с радиусом 3 и диаметром 9.

Вариант 22

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Опишите построение n-вершинного графа, у которого центр состоит из 3 вершин.

_________________________________________________________________

Вариант 23

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Описать n-вершинный граф, если эксцентриситеты всех его вершин равны n/2 .

_______________________________________________________________________

Вариант 24

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Построить граф с радиусом 5 и диаметром 10.

Вариант 25

1) Построить связные графы с данными степенными последовательностями или доказать, что таких графов не существует:

а)

б)

в)

2) Для построенных графов найти

а) метрические характеристики;

б) какие-нибудь остовные, порожденные подграфы и подграф, не являющийся остовным и порожденным;

в) дополнительный граф;

г) цепи, простую и не простую, не являющиеся циклами; циклы, простой и не простой; маршрут, не являющийся цепью;

д) матрицу смежности вершин.

3) Опишите построение n-вершинного графа, у которого центр состоит из 4 вершин.

Вариант  БИК-16

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	Шпак Софья