Прочие связанные определенияСтр 1 из 2Следующая ⇒
Ориентированный граф Ориентированный граф (сокращённо орграф) — это упорядоченная пара , для которой выполнены следующие условия: · — это непустое множество вершин или узлов, · — это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами. Дуга — это упорядоченная пара вершин , где вершину называют началом, а — концом дуги. Можно сказать, что дуга ведёт от вершины к вершине . Смешанный граф Смешанный граф — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными. Записывается упорядоченной тройкой , где , и определены так же, как выше. Ориентированный и неориентированный графы являются частными случаями смешанного. Изоморфные графы Граф называется изоморфным графу , если существует биекция из множества вершин графа в множество вершин графа , обладающая следующим свойством: если в графе есть ребро из вершины в вершину , то в графе должно быть ребро из вершины в вершину и наоборот — если в графе есть ребро из вершины в вершину , то в графе должно быть ребро из вершины в вершину . В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра. Прочие связанные определения Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром. Ориентированным путём в орграфе называют конечную последовательность вершин , для которой все пары являются (ориентированными) рёбрами. Циклом называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины и являются концами некоторого ребра, то согласно данному определению, последовательность является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия. Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что: · Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины. · Всякий простой неэлементарный путь содержит элементарный цикл. · Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро). · Петля — элементарный цикл. Бинарное отношение на множестве вершин графа, заданное как «существует путь из в », является отношением эквивалентности и, следовательно, разбивает это множество на классы эквивалентности, называемые компонентами связности графа. Если у графа ровно одна компонента связности, то граф связный. На компоненте связности можно ввести понятие расстояниямежду вершинами как минимальную длину пути, соединяющего эти вершины. Всякий максимальный связный подграф графа G называется связной компонентой (или просто компонентой) графа . Слово «максимальный» означает максимальный относительно включения, то есть не содержащийся в связном подграфе с большим числом элементов Ребро графа называется мостом, если его удаление увеличивает число компонент. ©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.
|