Многие задачи сводятся к рассмотрению совокупности объектов, существенные свойства которых описываются связями между ними. Например, при изучении электрических цепей на первый план может выступать характер соединений различных её компонентов – резисторов, м/с, источников и т. п.
В подобных случаях удобно рассматриваемые объекты изображать точками, называемые вершинами, а связи между ними – линиями, называемые ребрами. Множество вершин (Х={х1, х2,…,хn}, ½Х½=n), связи между которыми определены множеством ребер (V={v1, v2,…,vm}, ½V½=m), называется графом и обозначают G= (X, V).
Леонард Эйлер –первая работа по графам в 1736 г., когда работал в Российской Академии (решение задачи о Кенигсбергских мостах). Можно ли совершить прогулку, чтобы, выйдя из любого места города, вернуться в него, пройдя один раз по каждому мосту? Эйлер доказал, что подобный маршрут имеется только для такого графа, каждая из вершин которого связана с четным числом ребер. Кирхгоф в середине прошлого века применил графы для анализа электрических цепей.
|
|
Орграф (ориентированный граф) – направление связи между вершинами указывается ребром со стрелкой. Ориентированное таким образом ребро называют дугой.
Взвешенный граф. Отображение связей между объектами с помощью графов может быть в приписывании ребрам и дугам некоторых количественных значений, качественных признаков, называемых весами. Это может быть порядковая нумерация ребер и дуг, указывающая на очередность их рассмотрения (приоритет или иерархия). Вес ребра или дуги может означать длину, число связей и т. д. Вес можно приписывать не только ребрам, дугам, но и вершинам.
|
|
|
|
|
|
|
|
|
|
Инцидентность. Если ребро соединяет пару вершин, то говорят, что ребро инцидентно этим вершинам, а вершина инцидентна ребру
Смежность. Любые две вершины графа называются смежными, если существует соединяющее эти вершины ребро. Если два ребра инцидентны одной и той же вершине, то они называются смежными.
Смежность – отношение между однородными объектами (вершинами), инцидентность – отношение между разнородными объектами (вершинами и ребрами).
Изоморфизм.
Графы G=(X,V) и Gx=(Xx,Vx), для которых сохраняется
отношение инцидентности, называется изоморфным.
|
|
Они различаются лишь начертанием.
Планарность. При конструировании ЭА
к топологическому чертежу часто предъявляется
требование расположения проводников схемы на
плоскости без пересечений. Возникает задача
определения планарности графа. Граф G=(X,V)
называется плоским, если он расположен на плоскости
таким образом, что ребра имеют общие точки лишь в
вершинах. Граф Gx=(Xx,Vx), изоморфный плоскому
G=(X,V), расположенный на плоскости и имеющий
пересечения ребер, называется планарным.
плоский планарный
Маршрут в графе - последовательность m ребер (не обязательно различных) (v1, v3, v2, v3, v5), (v5, v6, v4, v4). Первый маршрут проходит через последовательность вершин (х1, х2, х3, х2, х3, х4) и соединяет вершины х1 и х4, а второй - через последовательность вершин (х3, х4, х4, х2, х4) и соединяет вершины х3 и х4. Число ребер в маршруте m называется его длиной.
Замкнутый маршрут приводит в ту же вершину, из которой он начался.
Цепь – маршрут, в котором нет повторяющихся ребер (v2, v5, v6).
Простая цепь – маршрут, все вершины которого различны (v1, v2, v5).
Циклом – называется последовательность ребер v1=(х1, хi),…, vk=(xj, x1), при которой в результате обхода вершин графа х1, хi,…,xj по этим ребрам возвращаются в исходную вершину x1. Каждое ребро в цикле встречается не более одного раза, вершины могут повторяться несколько раз. Цикл - замкнутая цепь (v2, v3, v4, v5).
Простой цикл – цикл, в котором нет повторяющихся вершин, кроме первой и последней (v2, v4, v5). Цикл называется сложным, если такие имеются.
Связный граф – граф, в котором перемещаясь из вершины в вершину, можно попасть в каждую вершину.
Деревья и лес. Дерево – связный неориентированный граф, не содержащий циклов. Дерево на множестве p вершин всегда содержится q=p-1 ребер, т.е. минимальное количество ребер для того, чтобы граф был связным. При добавлении в дерево ребра образуется цикл, а при удалении хотя бы одного ребра дерево распадается на компоненты (два дерева или дерево и изолированная вершина). Несвязный граф, компоненты которого являются деревьями, называется лесом.
Добавленное
|
Дерево Образование цикла Лес
Неориентированный граф G=(X,V) с множеством вершин Х и множеством ребер V может быть задан в числовой форме матрицей инциденций C=||c ij || nxm, в которой элемент c ij =1, если вершина хi инцидентна ребру v j, и c ij =0 в противном случае.
v1 v2 v3 v4 v5 v6 | |
x1 | 1 0 0 0 0 0 |
x2 | 1 1 1 1 0 0 |
C = x3 | 0 1 1 0 1 0 |
x4 | 0 0 0 1 1 1 |