рефераты конспекты курсовые дипломные лекции шпоры

Раздел Математика
/
Изоморфизм графов

Реферат Курсовая Конспект

Выберите учебное заведение

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

Изоморфизм графов - раздел Математика, Множество. Подмножество, собственное подмножество. Отношение принадлежности. Отношение включения В Теории Графов Изоморфизмом Графов ...

В теории графов изоморфизмом графов и называется биекция между множествами вершин графов такая, что любые две вершины и графа смежны, тогда и только тогда, когда вершины и смежны в графе . Здесь графы понимаются неориентированными и не имеющими весов вершин и ребер. В случае, если понятие изоморфизма применяется к ориентированным или взвешенным графам, накладываются дополнительные ограничения на сохранение ориентации дуг и значений весов. Если изоморфизм графов установлен, они называются изоморфными и обозначаются как . Иногда биекция записывается в виде подстановки изоморфизма . Некоторые задачи обработки графов требуют не только проверки изоморфизма, но и выяснения его подстановки.Отношение изоморфизма графов представляет собой отношение эквивалентности, определенное для графов, и позволяет произвести разбиение исходного класса всех графов наклассы эквивалентности. Множество графов, изоморфных друг другу, называется классом изоморфизма графов (англ.), их число в зависимости от представляет собой последовательность A000088 в OEIS (1, 1, 2, 4, 11, 34, 156, 1044, 12346, ...).

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

38.Матрицы и циклы в неориентированном графе.Для алгебраического задания графов используются матрицы смежности и инцидентности. Матрица смежностиA =(a_ij) определяется одинаково для ориентированного и неориентированного графов. Это квадратная матрица порядка n, где n - число вершин, у которой: a_ij = Для неориентированного графа матрица инцидентности B задается следующим образом: b_i =

Пусть G - неориентированный граф. Маршрутом или цепью в G называется такая последовательность (конечная или бесконечная) ребер a₁, a₂,... a_n..., что каждые соседние два ребра a_i и a_i+₁ имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз Длиной (или мощностью) маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько оно входит в данный маршрут. Замкнутый маршрут называется циклом.Маршрут (цикл), в которой все ребра различны, называется простой цепью (циклом). Маршрут (цикл), в которой все вершины, (кроме первой и последней), различны, называется элементарной цепью (циклом).

39.Пути и контуры в ориентированном графе. Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги. Число дуг пути называется длиной пути. Путь называется контуром, если его начальная вершина совпадает с конечной вершиной. Путь (контур), в котором все дуги различны, называется простым. Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным

40.Связость графа.Неориентированный граф называется связным, если каждая пара различных вершин может быть соединена по крайней мере одной цепью.

Ориентированный граф называется сильно связным, если для любых двух его вершин x_i и x_j существует хотя бы один путь, соединяющий x_i с x_j. Ориентированный граф называется односторонне связным, если для любых двух его вершин по крайней мере одна достижима из другой. Компонентойсвязности неориентированного графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа данного графа (максимально связный подграф). Компонентой сильной связности ориентированного графа называется его сильно связный подграф, не являющийся собственным подграфом никакого другого сильно связного подграфа данного графа (максимально сильно связный подграф). Компонентой одностронней связности неориентированного графа называется его односторонне связный подграф, не являющийся собственным подграфом никакого другого односторонне связного подграфа данного графа (максимально односторонне связный подграф).

41. Экстремальные пути в нагруженных ориентированных графах. Ориентированный граф называется нагруженным,если дугам этого графа поставлены в соответствие веса, так что дуге (x_i,x_j) сопоставлено некоторое число c(x_i,x_j) = c_ij, называемое длиной(или весом,или стоимостьюдуги). Длиной(или весом или стоимостью) пути s, состоящего из некоторой последовательности дуг (x_i,x_j), называется число l(s), равное сумме длин дуг, входящих в этот путь, т.е. l(s) = Е c_ij, причем суммирование ведется по всем дугам (x_i, x_j)s.Матрица C = (c_ij) называется матрицей длин дуг или матрицей весов.

Для ненагруженного графа введем понятие кратчайшего пути. Это путь с минимальным общим числом дуг, причем каждая дуга считается столько раз, сколько она содержится в этом пути В общем случае задача решается с помощью алгоритмов Флойда, Форда, Беллмана Алгоритмы нахождения минимального пути могут быть использованы для поиска кратчайших путей в ориентированном графе без контуров. Для этого нужно каждой дуге приписать вес, равный единице.

42.Алгоритм Форда – Беллмана нахождения минимального пути

Развернуть

Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Множество. Подмножество, собственное подмножество. Отношение принадлежности. Отношение включения

Пусть r отношение эквивалентности на множестве X и x Icirc X Классом эквивалентности порожденным элементом x называется подмножество множества... Таким образом x y Icirc X xry... Классы эквивалентности образуют разбиение множества X т е систему непустых попарно непересекающихся его...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Изоморфизм графов

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Множество. Подмножество, собственное подмножество. Отношение принадлежности. Отношение включения.
Мно́жество — одно из ключевых понятий математики, в частности, теории множеств и логики. Понятие множества обычно принимается за одно из исходных (аксиоматических) понятий, то есть не сводимое

Основные тождества алгебры множеств
Для любых множеств A, B, C справедливы следующие тождества: 1. Коммутативность. а) A È B = B È A (для

Основные тождества алгебры множеств
Для произвольных множеств А, В, и С справедливы следующие соотношения 1. Коммутативность объединения

Алгебра множеств. Осн. тождества алгеб. множеств
Множества вместе с определенными на них операциями образуют алгебру множеств. Последовательность выполнения операций задается с помощью формулы алгебры множеств. Например,

Упорядоченная пара, прямое декартово произведение
Если задана пара {a, b} , то множество {a, {a, b}} называется упорядоченной парой и обозначается(a, b) . При этом элемент a называется первым элементом, а элемент b — вторым элементом пары. В форма

Композиция отношений
Композицией (произведением, суперпозицией) бинарных отношений и

Симметричность
Симметричность в математике и логике, свойство бинарных (двуместных, двучленных) отношений, выражающее независимость выполнимости данного отношения для какой-либо пары объектов от порядка, в которо

Транзитивность
свойство бинарных (двуместных) отношений: отношение R наз. т р а н з и т и в н ы м, если для любых элементов х, у и z множества, на к-ром определено это отношение, из xRy и yRz следует xRz. Примера

Сюръективность, инъективность, биективность
Определение. Функция (отображение) f называется сюръективной или просто сюръекцией, если ля любого элемента y

Эквивалентность
Теорема: каждое отношение эквивалентности, определенное на А, соответствует некоторому разбиению множества А. Всякое разбиение множества А соответствует некоторому отношению эквива

Отношения частичного порядка
Отношение r называется отношением частичного порядка (или просто частичным порядком) на множестве X, если оно рефлексивно, антисимметрично и транзитивно на множестве X.

Рекурсивная процедура
Процедура называется рекурсивной, если она прямо или косвенно обращается к себе самой. Рекурсия является естественным свойством для большого числа математических и вычислительных алгоритмов. Важно

N_местная функция
Используя канторовскую функцию с, можно определить последовательность общерекурсивных функций такую что - n_местная функция, осуществляющая взаимно-однозначное отображение : Для любого сущ

Определение булевой функции
Булевой функцией f(x1, x2, ... , xn) называется произвольная функция n переменных, аргументы которой x

Формулы логики булевых функций
Формула логики булевых функций определяется индуктивно следующим образом: 1. Любая переменная, а также константы 0 и 1 есть формула. 2. Если A и B – формулы,

Вопр. Равносильные преобразования формул
В отличие от табличного задания представление функции формулой не единственно. Например, две различные формулы x1Vx2 и (x

Булева алгебра (алгебра логики). Полные системы булевых функций.
Булевой алгеброй - называется непустое множество A с двумя бинарными операциями (

Основные характеристики графов.
В математической теории графов и информатике граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами). Объекты представляются как

Основные свойства матриц смежности и инцидентности
— Матрица смежности неориентированного графа является симметричной, для ориентированного графа это не верно. — Сумма элементов i-той строки/i-того столбца матрицы смежности неориентированн

Предполагается, что ориентированный граф не содержит контуров отрицательной длины.
Алгоритм 3.1 (Алгоритм Форда – Беллмана). Основными вычисляемыми величинами этого алгоритма являются величины j(k), где i = 1, 2, … , n

Деревья. Основные определения
Неориентированным деревом(или просто деревом) называется связный граф без циклов. Этому определению эквивалентны, как легко показать, следующие определения: а) дерево есть св

Минимальные остовные деревья нагруженных графов
Граф G = (X, A) называется нагруженным, если для каждого ребра (xi,xj) определена его длина (или вес) cij.

Основные задачи управления
Задачами теории управления являются: · синтез структуры и параметров объекта управления, соответствующих цели (закону функционирования) создаваемой системы с управлением;

Структура системы с управлением
В теории управления принято считать, что системы с управлением создаются для достижения конкретных целей, которые определяются в рамках других наук, занимающихся исследованием конкретных систем. В

Цель автоматизации управления
В общем случае, систему управления можно рассматривать в виде совокупности взаимосвязанных управленческих процессов и объектов. Обобщенной целью автоматизации управления является повышение эффектив

Состав задачи системного анализа в процессе создания информационных систем
В состав задач системного анализа в процессе создания информационных систем входят задачи декомпозиции, анализа и синтеза. Задачи декомпозиции: означает представление системы в виде подсис

Система как Семантическая модель
Семантическая модель - представление понятий в виде графа, в вершинах которого расположены понятия, в терминальных вершинах - элементарные понятия, а дуги представляют отношения ме

Понятие и модели сложных систем.
Центральной концепцией теории систем, кибернетики, системного подхода, всей системологии является понятие «системы».Первое определение системы.Начнем с рассмотрения искусственных, т.е. создаваемых

Система как семантическая модель.
Сущность любой системы и любого ее элемента могут быть адекватно поняты только в их взаимодействии с другими окружающими системами и другими элементами. Познание сути вещей означает познание их вза

Задача на условный экстремум(общий алгоритм). Функция Лагранжа
Алгоритмнеопределённогомножителей Лагранжа для нахождения условного экстремума: Составляется функция Лагранжа: