Кортежирование графов
Понятие кортежа, как и понятие множества, является одним из основных математических понятий, поэтому для него также не существует определения через другие понятия. Интуитивно кортеж можно определить как упорядоченный набор компонентов. Кортежи одинаковы (равны), если они состоят из одних и тех же компонентов, причем порядок этих компонентов также одинаков.
Компоненты кортежей обычно перечисляются в круглых скобках.
Например, a = (3, 8, 2) – кортеж. Числа 3, 8, 2 – его компоненты. Другой пример кортежа – c = (8, 2, 3). Кортежи a и c – разные.
В кортеже могут быть одинаковые элементы. Например, x = (8, 3, 2, 3) и y = (3, 8, 2, 3) – кортежи, причем разные.
Количество компонентов в кортеже называется его длиной. Например, длина кортежей a и c равна трем, а кортежей x и y – четырем. Кортежи из двух компонентов называют парами, из трех – тройками, и т.д.
Простейший пример кортежа – вектор, задающий координаты точки на плоскости или в пространстве. Очевидно, что, например, точки на плоскости с координатами (5, 7) и (7, 5) – разные.
Как и для множеств, компоненты кортежей могут быть любыми (не только числами). Например, перечень студентов учебной группы, упорядоченный по их среднему баллу за время учебы, можно считать кортежем.
В математике, Граф — это абстрактное представление множества объектов и связей между ними. Графом называют пару (V, E) где V это множество вершин, а E множество пар, каждая из которых представляет собой связь (эти пары называют рёбрами).
Граф может быть ориентированным или неориентированным. В ориентированном графе, связи являются направленными (то есть пары в E являются упорядоченными, например, пары (a, b) и (b, a) это две разные связи). В свою очередь в неориентированном графе, связи ненаправленные, и поэтому если существует связь (a, b) то значит, что существует связь (b, a).
|
|
Пусть даны множества X1,X2,...,Xn. Кортежем длины n, составленным из элементов этих множеств, называется конечная последовательность α=(x1,x2,..,xk), где для всех k, 1≤k≤n, xk∈Xk.
Элемент xk называется k-й координатой или k-й компонентой кортежа α.
Два кортежа равны в том и только том случае, когда они имеют одинаковую длину и их соответствующие координаты равны, т.е. кортежи α=(x1,...,xm) и β=(y1,...,yn) равны только в том случае, когда m=n и xk=yk для всех 1≤k≤n.
Кортежи длины два называются упорядоченными парами, длины три — упорядоченными тройками, длины n — упорядоченными n-ками. Для краткости слово “упорядоченные” обычно опускают.
Кортеж, не содержащий ни одной координаты, имеет длину 0 и называется пустым.
Пусть даны множества A,B. Прямым (декартовым) произведением множеств A и B называется множество, состоящее из пар (a,b), где a∈A и b∈B, обозначается A×B.
n-й декартовой степенью множества A называется его прямое n-кратное произведение на самого себя, обозначается: An.
An=A×An−1
Многие математические объекты формально определяются как кортежи. Например, ориентированный граф определяется как пара (V,E) где V — это множество вершин, а E — подмножество пар в V×V, соответствующих дугам графа. Точка в n -мерном пространстве действительных чисел определяется как кортеж длины n, составленный из элементов множества действительных чисел.
Во многих задачах, особенно, решаемых на ЭВМ, графы удобно описывать матрицами.
|
|
1. Задание графов матрицей смежности:
Матрица смежности – это квадратная матрица порядка p (количество вершин), элемент которой, стоящий в i строке и j столбце определяется по правилу:
2. Задание графов матрицей инцидентций.
Матрицей инцидентции называется прямоугольная матрица размерности 
(p –количество вершин, q – количество ребер), элемент которой стоящий в i строке и j столбце определяется по правилу:
- для неориентированного графа.
- для ориентированного графа.
Список использованных источников
1. Кортежи и декартово произведение множеств. URL: https://it.rfei.ru/course/~mBme/~6v6/~0pCLCk (дата обращения: 17.12.2018).
2. Алгоритмы на графах. URL: https://habr.com/post/65367/ (дата обращения: 17.12.2018).
3. Невидомская И.А. Математическое моделирование экономических ситуаций на основе выбора оптимальной стратегии по управлению бизнесом // Сб. науч. статей по материалам III Всероссийской конференции. - Ставрополь, 2010. - С. 165-169.
4. Долгополова А.Ф., Гулай Т.А., Литвин Д.Б. Особенности применения методов математического моделирования в экономических исследованиях // Kant: Экономика и управление. 2013. № 1. С. 62-66.