Персональный сайт - Смежные вершины, матрица смежности для графа и ортграфа: определение пример

Тот кто придумал летнюю сессию, того нужно сжечь на костре!

Главная
Дискретка (экзамен)

1) Понятия множества и элемента можества, примеры. Подмножество, собственное подмножество: определения, примеры. Универсальное множество: определение, пример
2) Равные множества: определение, пример. Мощность конечного множества, пустое множество: определение, примеры
3) Способы задания множества
4) Объединение и пересечение множеств: определение, примеры
5) Разность множеств, дополнение множеств: определения и примеры
6) Основные тождества теории множеств. Привести пример доказательства для одного из тождеств
7) Прямое (декартово) произведение множеств: определение и пример
8) Мощность декартова произведения конечных множеств
9) Соответствие между множествами: определение, пример. Область определения и область значений соответствия
10) Всюду определенное соответстие, сюръективное соответствие: определение, примеры
11) Образ элемента при соответствии, прообраз элемента при соответствии: определение, примеры. Функциональное соответствие (функция): определение, пример
12) Взаимно однозначное соответствие: определение, пример
13) Отображение множества в (на) множество: определение, пример
14) Обратное соответствие: определение, пример
15) Композиция функций: определение, пример
16) Бинарное отношение на множестве: определение, пример
17) Свойства бинарного отношения: рефлексивность, симметричность, транзитивность
18) Отношение эквивалентности, разбиение множества на классы эквивалентности
19) Антирефлексивность и антисимметричность; отношение строгого и нестрогого порядков
20) Определение и пример логической функции
21) Логические функции: отрицание, дизъюнкция, конъюнкция
22) Логические функции: сложение по модулю 2, импликация, эквивалентность
23) Суперпозиция логических функций; логические формулы; равносильные логические формулы
24) Теорема о дизъюнктивной нормальной форме логической функции
25) Булевы операции и их основные свойства. Привести док-во одного из свойств
26) Функциональная полная система логических функций: определение, пример
27) Граф, вершина графа, ребро графа: определения, примеры
28) Ортграф, вершина ортграфа, дуга графа: определение примеры
29) Смежные вершины, матрица смежности для графа и ортграфа: определение пример
30) Инцедентные вершина и ребро, матрица инцендентности для графа и ортграфа: определение пример
31) Диаграмма графа, изоморфизм графов
32) Плоские графы. Формула Эйлера
33) Мультиграф и псевдограф: определения и пример
34) Степень вершины, вычисление степени вершины по элементам матрицы смежности. Изолированная и висячая вершины: определение, примеры
35) Полустепени захода и исхода вершины ортграфа, вычисление полустепеней по элементам матрицы смежности
36) Матрицы смежности и инцедентности изоморфных графов
37) Маршрут, цепь, простая цепь, цикл: определение примеры
38) Ориентированный маршрут, цепь, путь, контур: определения примеры
39) Подграф, остовный подграф: определение пример
40) Связный граф, компоненты графа: определения и примеры. Точка сочленения и мост: определение пример
41) Числа реберной и вершинной связности: определения пример
42) Объединение, произведение, композиция графов: определение пример
43) Дерево: дать равносильное определение понятию, привести пример
44) Ориентация графа, определить число всех возможных ориентаций для графа с заданным числом ребер
45) Остовное дерево: определение пример. Алгоритм построения остовного дерева
46) Взвешенный граф, минимальное остовное дерево: определение пример
47) Обоснование алгоритма построения минимального остовного дерева
48) Путь, контур, полупуть, полуконтур в ортграфе: определение пример. Сильный, односторонний, слабый ортграф: определение пример
49) Сильная, односторонняя и слабая компоненты ортграфа: определения и примеры. Конденсация графа: определение пример
50) База ортграфа: определение пример. Док-во теоремы о базе графов
51) Алгоритм Дейкстры поискакратчайшего пути между двумя выделенными вершинами ортграфа
52) Алгоритм Флойда поиска кратчаших путей между всеми парами вершин ортграфа. Встроенный и внешний способы восстановления пути.
53) Эйлеров граф: определение и пример. Доказать критерий существования в графе эйлерова цикла
54) Алгоритм Флёри построения эйлерова цикла. Обоснование алгоритма Флёри
55) Гамильтонов цикл. Достаточные условия наличия в графе гамильтонова цикла

Если ребро L={Vi, Vj}принадлежит множеству Е, то Vi, Vj - сменые вершины, говорят так же что ребро L - инцедентное, вершинам Vi, Vj.

Если в графе любые 2 вершины смежные, то граф называется полным

Создать бесплатный сайт с uCoz