Контрольная работа по "Дискретной математике"

1. Перестановки

1. Перестановкой без повторений из n элементов называется любой упорядоченный набор этих n элементов
2. Если в перестановках из n (общего числа элементов) есть k различных элементов, и при этом первый элемент повторяется n1 раз, второй элемент повторяется n2 раз, …, k-ый элемент повторяется nk раз (n1 + n2 + … + nk = n), то такие перестановки называются перестановками с повторениями.

1. Размещения  

1. Размещением без повторений из n элементов по k называется упорядоченный набор из k различных элементов.
2. Размещением с повторениями из n элементов по k называется упорядоченный набор из k элементов, при этом элементы могут повторяться

1. Сочетания

1. Сочетанием без повторений из n элементов по k называется любое k-элементное подмножество заданного n-элементного множества
2. Пусть есть множество M, состоящее из n элементов

(M = {a1, a2, …, an}).

Пусть нужно выбрать подмножество множества M, состоящее из k элементов, при этом элементы могут повторяться, это называется сочетанием из n по k с повторениями

1. Граф

1. Графом называется совокупность 2-х множеств V, E, где V – непустое множество, а [pic 1]

1. Петля в графе

1. Пусть задан граф . Пары  называются петлями графа[pic 2][pic 3]

1. Кратность ребра

1. Пусть задан граф . Количество одинаковых пар во множестве E называется кратностью соответствующего ребра[pic 4]

1. Псевдограф

1. Если в графе есть и петли, и кратные ребра, то такой граф называется псевдографом

1. Мультиграф

1. Если в графе есть кратные ребра, но нет петель, то такой граф называется мультиграфом 

1. Простой граф

1. Если в графе отсутствуют кратные ребра и петли, то такой граф называется простым

1. Ориентированный граф

1. Если для ребер графа задана ориентация (ребра упорядочены), то граф называется ориентированным (орграфом)

1. Неориентированный граф

1. Если для ребер графа не задана ориентация, то граф называется неориентированным

1. Полный граф

1. Простой неориентированный граф называется полным графом, если две любые вершины этого графа смежны

1. Двудольный граф

1. Граф называется двудольным графом, если множество его вершин можно разделить на 2 подмножества V1 и V2, которые называются долями графа , так, что вершины в графе могут быть смежны только если они принадлежат разным долям графа[pic 5]

1. Смежность вершин  

1. Если в графе есть ребро , то говорят, что вершины u, v называют смежными[pic 6]

1. Инцидентность вершин

1. Если в графе есть ребро , то говорят, что вершины u, v инцидентны ребру e[pic 7]

1. Степень вершины

1. Пусть задан неориентированный граф . Степенью вершины u называется количество ребер инцидентных данной вершине. Петля считается 2 раза.[pic 8]

1. Изолированные вершины  

1. Если степень вершины равна 0, то вершина называется изолированной

1. Висячие вершины

1. Если степень вершины равна 1, то вершина называется висячей

1. Полустепень захода вершины

1. Полустепенью захода вершины v орграфа называется количество ребер, заходящих в данную вершину δ+(v)

1. Полустепень исхода вершины

1. Полустепенью исхода вершины v орграфа называется количество ребер, исходящих из данной вершины δ-(v)

1. Матрица смежности

1. Матрицей смежности вершин графа (орграфа) называется квадратная матрица A размерности n, в которой aij = k, где k – количество ребер вида (vi, vj)

1. Матрица инцидентности  

1. Пусть  – неориентированный граф.[pic 9]

Матрицей инцидентности графа G называется матрица B размерности n x m, где n = |V|, m = |E|, в которой

[pic 10]

1. Пусть  – ориентированный граф.[pic 11]

Матрицей инцидентности графа G называется матрица B размерности n x m, где n = |V|, m = |E|, в которой

[pic 12]

1. Операция подразбиения ребра

1. Операция подразбиения ребра (u, v) состоит в удалении этого ребра, добавлении вершины w и добавлении двух новых ребер (u, w) и (w, v)

1. Изоморфизм графов

1. Графы G1 = (V1, E1) и G2 = (V2, E2) называются изоморфными, если существуют биективные отображения ϕ1: V1 -> V2,

ϕ2: E1 -> E2, такие, что

 [pic 13]

1. Гомеоморфизм графов

1. Графы G1 и G2 называются гомеоморфными, если существуют их подразбиения, которые изоморфны

1. Маршрут

1. Маршрутом для графа называется последовательность

, в которой чередуются вершины и ребра, и ребро es = (vs, vs+1), v1 – начало маршрута, vk – конец маршрута[pic 14]