No Image

Что такое связный граф

СОДЕРЖАНИЕ
0 просмотров
10 марта 2020

связный граф — — [http://www.iks media.ru/glossary/index.html?gloss >Справочник технического переводчика

Связный граф — 8. Связный граф По ГОСТ 19880 74 Источник: ГОСТ 23070 78: Анализ и оптимизация на ЭВМ радиоэлектронных схем. Термины и определения … Словарь-справочник терминов нормативно-технической документации

граф — Графическое изображение электрической цепи, в котором ветви электрической цепи представлены отрезками, называемыми ветвями графа, а узлы электрической цепи — точками, называемыми узлами графа. [ГОСТ Р 52002 2003] граф Основное понятие и… … Справочник технического переводчика

Граф — [graph] основное понятие и объект изучения теории графов, математически определяется двояко. С одной стороны как совокупность двух множеств: множества элементов x Î X и множества соответствий, отношений между этими элементами t Î T. С другой… … Экономико-математический словарь

Граф (математика) — У этого термина существуют и другие значения, см. Граф (значения). Неориентированный граф с шестью вершинами и семью рёбрами В математической теории графов и информатике граф это совокупность непустого множества вершин и множества пар… … Википедия

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

Связный список — В информатике, связный список базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.[1] Принципиальным… … Википедия

Граф-схема алгоритма — Ждущая вершина алгоритма Граф схема алгоритма (ГСА) конечный связный ориентированный граф , вершины которого соответствуют операторам, а дуги … Википедия

Читайте также:  Магия крови в играх

ГРАФ — множество Vвершин и набор Енеупорядоченных и упорядоченных пар вершин; обозначается Г. через . Неупорядоченная пара вершин наз. ребром, упорядоченная пара дугой. Г., содержащий только ребра, наз. неориентированным; Г., содержащий только дуги,… … Математическая энциклопедия

Вершина (граф) — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф … Википедия

Граф – совокупность двух множеств G = (V, X), где V = 1, …, vn> – множество вершин, X=<(vi, vj) | vi, vj Î V> – множество ребер т.е. граф – совокупность вершин и соединяющих их ребер. При этом дуга (vi, vj) называется исходящей из вершины vi и заходящей в вершину vj.

Псевдограф– граф с кратными (одинаковыми) ребрами и петлями.

Мультиграф– псеводограф без петель.

Элементарный граф (или просто граф) – мультиграф с кратностью ребер =1.

Неориентированный граф – граф, пары множества X которого неупорядочены, называются ребрами.

Ориентированный граф– граф, у которого пары множества Х упорядочены, называются дугами, обозначаются (v,w). Орграф можно задать как D=(V, Г), где Г – многозначное отображение множества вершин в себя, V – множество вершин.

Операции с графами:

2)Пересечение графов G1 (V1, X1) и G2 (V2, X2) называется граф G1 Ç G2=(V1 Ç V2, X1 Ç X2) [т.е. граф, содержащий все вершины и дуги, принадлежащие одновременно графам G1 и G2].

3)Декартово произведение орграфов G1 (V1, X1) и G2 (V2, X2) называется граф G1 x G2 = (V1 x V2, Г), где для каждой вершины U = (v, w) Î V : Гu = Гv x Гw.

Связность графа, сильно связный граф:

Неориентированный граф G называется связным, если существует путь между любыми двумя его вершинами vi и vj. (любая его вершина достижима из другой вершины)

Читайте также:  Интерактивный оконный терминал windows 7

Ориентированный граф D называется сильно связным, если любые две его вершины vi и vj взаимодостижимы [т.е. существуют пути из vi в vj и из vj в vi].

Орграф D называется односторонне связный, если для любых двух его вершины vi и vj хотя бы одна достижима из другой.

Орграф D называется слабосвязным, если ассоциированный с ним неориентированный граф G является связным (получается замещением дуг на ребра)

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

Гv – образ вершины v. Гv 2 – образ вершин которые достижимы из v (находятся в образе вершины v)

Прямым транзитивным замыканием вершины v называется множество вершин, достижимых из v.

Гv -1 – прообраз вершины v. Гv 2 – прообраз вершин которые являются прообразами v (те, из которых достижима v)

Обратным транзитивным замыканием вершины v называется множество вершин, из которых достижима v.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Для студентов недели бывают четные, нечетные и зачетные. 9637 — | 7525 — или читать все.

91.146.8.87 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Определение связных и несвязных графов

Граф G(V,E) называется связным, если для любой пары различных вершин этого графа существует цепь, соединяющая эти вершины. Так как из существования цепи, соединяющей две вершины графа, следует существование простой цепи, соединяющей эти вершины (см. следствие 2 к упражнению 1 из пункта 1.10), то граф является связным, если любую пару его вершин соединяет по крайней мере одна простая цепь. Если для графа G(V,E) можно указать пару различных вершин, которые не соединяются цепью (простой цепью), то граф называется несвязным. Например, на рис. 1, 3, 6, 7а, 16, 8а, 9-12, 16- 18, 19а-19г, 20-23, 25 представлены связные графы, а на рис. 4 — несвязный граф.

Читайте также:  Где в вин 10 удаление программ

Теорема 4. Граф G(V, Е) является несвязным тогда и только тогда, когда множество его вершин V можно разбить на два не пустых подмножества V/ и У2 так, чтобы любое ребро графа соединяло вершины из одного подмножества.

Доказательство. Пусть G(V,E) — несвязный граф. Зафиксируем некоторую вершину А графа и обозначим через Vi множество, состоящее из вершины А и всех тех вершин из V, которые соединены цепями с вершиной А. Множество V/ не пусто (оно содержит, по крайней мере, вершину А) и не совпадает со множеством V (в противном случае граф G(V, Е) — связный, так как между его любыми двумя различными вершинами существует цепь, проходящая через А). Рассмотрим дополнение V2=V-Vi. Множество V2 не пусто. Ясно, что никакое ребро графа G(V,E) не соединяет ни одну вершину из V/ ни с одной вершиной из V2. Поэтому построенные множества V/ и V2 образуют искомое разбиение множества V.

Обратно, пусть существует разбиение V = V/ U V2t удовлетворяющее условию теоремы. Докажем, что G(V,E) — несвязный граф. Рассмотрим произвольную пару вершин из разных подмножеств AG V/, Be V2, и докажем, что не существует цепи, соединяющей эти вершины. Действительно, если такая цепь существует, то она включает ребро, граничные точки которого принадлежат разным подмножествам, что противоречит условию. Теорема доказана.

Комментировать
0 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector