Графы. Основные понятия и определения (вершины, ребра, петли, кратность ребра, псевдограф, мультиграф, граф, орграф, неориентированный граф). Привести примеры.

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

Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах граф

Совокупность множества вершин и множества ребер, причем каждое ребро связано отношением инцидентности с двумя вершинами; другими словами, каждое ребро является связью двух вершин

Графом G(X, U) называют совокупность множества вершин X = (x1, x2, …, xn) и ребер U = (u1, u2, …, um), если каждое ребро

инцидентно двум вершинам, другими словами, является связью двух вершин. В частном случае в качестве этих двух вершин может дважды выступать одна и та же вершина, тогда ребро называется петлей. Инцидентность - отношение типа "лежит на" или "проходит через". Если связываемые вершины xi и xj в (1) упорядочены, то ребро становится направленным и называется дугой. Граф с направленными связями называют направленным графом (ориентированным графом или орграфом), в противном случае — ненаправленным (неориентированным). Граф называют смешанным, если в нем имеются как ребра, так и дуги. Ребра, соединяющие одинаковые вершины, — кратные или параллельные. Граф без петель, но с кратными ребрами — мультиграф. графа как совокупности двух множеств V (точек) и Е (линий), между элементами которых определено отношение инцидентности, причем каждый элемент е  Е инцидентен ровно двум элементам v', v"  V. Элементы множества V называются вершинами графа G, элементы множества Е – егоребрами. Направленные ребра часто называют дугами. Различные ребра могут быть инцидентны одной и той же паре вершин (рис. 3.1, е), в этом случае они называются кратными; граф, содержащий кратные ребра, часто называют мультиграфом. Ребро может соединять некоторую вершину саму с собой (рис. 3.1,ж), такое ребро называется петлей. Песевдограф допускает и кратные ребра, и петли.

Рис. 3.1. Примеры изображения неориентированных графов

27. Графы. Смежность, инцидентность, степени (концы ребра, начало и конец дуги, инцидентность, смежность вершин, смежность ребер, степень вершины, изолированные вершины, висячие вершины, полустепень исхода (захода)). Привести примеры.

Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга   ведёт от вершины v к вершине w. Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}.  Инцидентность Отношение типа "лежит на..." или "проходит через..." между двумя объектами

Число инцидентных вершине ребер называется степенью вершины и обозначается P(X i).  Вершина, степень которой равно 0, называется изолированной. висячей (или листом), если она является концом ровно одного ребра.