Контрольные вопросы

1. Пусть x  X, y  Y и R – отношение между элементами множества, выражаемое соотношением xRy. Укажите, в каких случаях R можно рассматривать как функцию?

а) X – множество студентов, Y – множество учебных дисциплин, xRy означает «x изучает y».

б) X – множество спортсменов, Y – рост в единицах длины, xRy означает «x имеет рост y».

2. Пусть А = -2, -1, 0, 1, 2, а В = 0, 1, 2, 3, 4, 5. Определим соответствие   А  В как  =  (-2, 5), (-1, 2), (0, 1), (2, 5). Каковы свойства соответствия f ?

3. Пусть   R  R, где R – множество действительных чисел. Найдите область значений и область определения следующих функций:

а) (х) = х ² + 4; б)  (х) = ;

4. Соответствие G определено графически. Найти образы и прообразы: чисел 1, 2, 4; отрезков [1, 2], [2, 4].

4. Виды графов

4.1. Понятие графа

Графом G(V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множества Е неупорядоченных пар различных элементов множества V (Е – множество ребер).

Число вершин графа (порядок графа) G обозначим p, а число ребер – q.

Пусть v₁, v₂ – вершины, е = (v₁, v₂) – соединяющее их ребро. Тогда вершина v₁ и ребро е инцидентны, вершина v₂ и ребро е также инцидентны. Два ребра, инцидентные одной вершине, называются смежными; две вершины, инцидентные одному ребру, также называются смежными. Таким образом, смежность есть отношение между однородными элементами графа, тогда как инцидентность – отношение между разнородными элементами.

П ример.

Данная диаграмма изображает граф, имеющий четыре вершины и пять ребер. В этом графе вершины v₁ и v₂ смежны, а вершины v₁ и v₃ не смежны. Смежные ребра: e₁ и e₅. Несмежные ребра: e₁ и e₃. Ребро е₁ инцидентно вершинам v₁ и v₂, вершина v₁ инцидентна ребрам е₁ и е₄.

Если элементами множества Е являются упорядоченные пары, то граф называется ориентированным (или орграфом). В этом случае элементы множества V называются узлами, а элементы множества Е – дугами.

Граф называют неориентированным, если он не имеет ориентированных ребер. Для краткости неориентированный граф называют также неографом. Иногда каждое ребро такого графа представляют как две дуги, направленные в противоположные стороны. Неориентированные графы можно считать частными случаями ориентированных графов, соответствующих симметричным бинарным отношениям, т.е. таким ориентированным графам, которые наряду с каждой дугой (u, v) содержат и дугу (v, u).

Граф, полученный после замены всех дуг в ориентированном графе на ребра, называется основанием.

Если элементом множества Е может быть пара одинаковых (не различных) элементов V, то такой элемент множества Е называется петлей, а граф называется графом с петлями (или псевдографом).

Если Е является не множеством, а набором, содержащим несколько одинаковых элементов, то эти элементы называются кратными (параллельными) ребрами, а граф называется мультиграфом или квазиграфом.

Максимальное число ребер, соединяющих две вершины графа, называется мультичислом графа.

Граф называется простым, если каждую пару вершин соединяет не более чем одно ребро и в графе отсутствуют петли.

Если вершины и/или ребра графа помечены (обозначены), то граф называется помеченным (или нагруженным). В качестве множества пометок обычно используются буквы или целые числа.

Граф, в котором каждая пара вершин смежна, называется полным. Полный граф с p вершинами обозначается K_p.

Граф G’(V’, E’) называется подграфом графа G(V, E) (обозначается G’  G), если V’  V, а E’ – множество всех ребер G, оба конца которых принадлежат V’.

Двудольный граф (или биграф, или четный граф) – это граф G(V, E), такой что множество V разбито на два непересекающихся множества V₁ и V₂, причем всякое ребро из Е соединяет вершину из V₁ с вершиной из V₂. Множества V₁ и V₂ называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V₁ и V₂, то он называется полным двудольным графом. Если V₁ = m и V₂ = n, то полный двудольный граф обозначается K_m,n.

П ример. Диаграмма графа K3,3.

Граф, состоящий из простого цикла с k вершинами, обозначается C_k.

Пример. С3 – треугольник.

Количество ребер, инцидентных вершине v, называется (локальной) степенью (или валентностью) вершины v и обозначается d(v):

0  d(v)  p – 1

Если степени всех вершин равны k, то граф называется регулярным (однородным) степени k.

П ример. Диаграмма регулярного графа степени 3.

Для орграфа число дуг, исходящих из вершины v, называется полустепенью исхода, а входящих – полустепенью захода. Обозначаются эти числа, соответственно, d^–(v) и d⁺(v).

Если в орграфе полустепень захода некоторой вершины равна нулю (т.е. d⁺(v) = 0), то такая вершина называется источником, если же нулю равна полустепень исхода (т.е. d^–(v) = 0), то вершина называется стоком.

Графы G₁ и G₂ равны, то есть G₁ = G₂, если их множества вершин и ребер совпадают: V₁ = V₂ и E₁ = E₂. Графы, отличающиеся только нумерацией вершин и ребер, называются изоморфными.

П ример.

Три внешне различные диаграммы являются диаграммами одного и того же графа.

Д ополнением графа G(V₁, E₁) называется граф G(V₂, E₂), где V₂ = V₁    E₂ =   = {e  V₁  V₁  e  E₁}.

G G