Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Прямое произведение множеств
|
|
Рассмотрим два непересекающихся множества A = {a1, a2, …, an} и B = {b1, b2, …, bm}. Выберем какой-либо элемент из множества A и припишем к нему справа некоторый элемент множества B. Получим упорядоченную пару. Элементы, образующие пару, будем записывать в круглых скобках, отделяя один элемент от другого запятой: (ai, bj), где ai ∈ A; bj ∈ B; i = 1, 2, 3, …, n; j = 1, 2, 3, …, m.
Множество всех упорядоченных пар (ai, bj) обычно называют декартовым произведением множеств А и В (иногда — прямым произведением). Для обозначения этой операции используется знак арифметического умножения: A × B.
A × B ≠ B × A, то есть операция декартова произведения некоммутативна. Кроме того, (A × B) 
(B × A) = ∅, если A B = ∅.
При этом множество A × B содержит те же пары, что и множество B × A, но порядок записи элементов в парах другой. Если же A B ≠ ∅, то и (A × B) (B × A) ≠ ∅.
Так как в общем случае операция декартова произведения некоммутативна, то всякая перестановка множеств в записи декартова произведения дает новое множество упорядоченных пар.
Операция декартова произведения множеств ассоциативна:
(A × B) × C = A × (B × C) = A × B × C, благодаря чему при записи декартова произведения нескольких множеств скобки можно не использовать.
Для декартова произведения множеств справедливы следующие законы дистрибутивности:
A × (B U C) = (A × B) U (A × C);
A × (B \ C) = (A × B) \ (A × C),
что позволяет раскрывать скобки в выражениях, содержащих операцию декартова произведения и операции объединения либо разности множеств.
Если |A| и |B| — кардинальные числа множеств A и B, то
|A × B| = |B × A| = |A| ⋅ |B|, где точка между символами |A| и |B| обозначает операцию арифметического умножения.
Чтобы определить число элементов декартова произведения нескольких множеств, достаточно найти арифметическое произведение их кардинальных чисел.
2. Определение графа
Граф – это множество V точек, определенным образом соединенных между собой линиями, необязательно прямыми.
Точки множества V называются вершинами графа, а соединяющие их линии – ребрами.
Всякий простой граф может быть представлен не только в виде рисунка, но и аналитически. Пусть E – множество ребер графа, тогда можно записать (рис.1):
V = {1, 2, 3, 4, 5, 6, 7};
E = {{1, 2}, {1, 3}, {1, 4}, {1, 7}, {2, 5}, {2, 6}, {2, 7}, {3, 4}, {3, 6}, {4, 5}, {4, 6}, {5, 7}}, где E – множество двухэлементных подмножеств множества V.
Существуют графы, в которых те или иные пары вершин соединены не одним ребром, а несколькими. Такие ребра называют кратными (параллельными).
Кроме того, граф может содержать ребра, соединяющие какую-либо вершину саму с собой. Такие ребра называются петлями.
Вершина называется изолированной, если у нее нет петель и из нее не выходит ни одного ребра.
Граф, содержащий петли или кратные ребра, называется псевдографом. Пример псевдографа приведен на рис. 2, где вершина 1 имеет кратные петли, вершина 2 – одиночную петлю, а вершины 2 и 3 соединены кратными ребрами.
Псевдограф без петель называется мультиграфом. Пример мультиграфа приведен на рис. 3.
Граф называется однородным, если степени всех его вершин равны между собой:
ρ (1) = ρ (2) = … = ρ (n), где n – число вершин графа; ρ (i) – степень i-й вершины графа (i = 1, 2, …, n).
Граф без петель называется полным, если каждая пара его вершин соединена одним ребром. Примеры полных графов приведены на рис. 9.
Граф, или неориентированный граф G — это упорядоченная пара G: = (V, E), для которой выполнены следующие условия:
§ V — это непустое множество вершин, или узлов,
§ E — это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами.
Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G: = (V, A), для которой выполнены следующие условия:
§ V — это непустое множество вершин или узлов,
§ A — это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.
Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга 
ведёт от вершины v к вершине w.
|
|