Алгоритм МАГУ – алгоритм построения НВУП методом МАГУ

Исходные данные: ║u_ij║- матрица инциденций;

Где n – множество вершин

r – множество рёбер.

Вычисляем произведение, в котором i-ый подмножитель есть сумма вершин инцидентных ребру u_iєU графа G.

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

xi+1=1 xi*1= xi xi+ xi= xi xi* xi= xi

u1 u2 u3 u4   х1         ║uij║= х2           х3           х4

Пример:

Составим произведение:

П=(х₃+ х₄) (х₁+ х₂) (х₁+ х₃) (х₂+ х₄)= (х₃х₁+ х₂х₃+ х₁х₄+х₂х₄) (х₁х₂+ х₁х₄+ х₂х₃+х₃х₄)= х₂х₃+ х₁х₄

F₁={ х₂,х₃}, F₂={ х₁,х₄} – НВУП.

30. Планарные графы. Ориентированные графы. Понятия плоского графа.

Плоский и планарный графы

Пусть имеется граф. Будем считать граф, укладывающийся на поверхность S или который можно нарисовать на ней так, чтобы никакие два ребра не пересекались бы, а также его можно было бы уложить на плоскости, планарным. Плоский граф – граф, уложенный на плоскости. Максимально планарным графом – называют граф, который перестаёт быть планарным при добавлении одного ребра.

Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные ребра именуются также дугами, а в некоторых источниках (Оре) и просто рёбрами.

Орграф, ориентированный граф G = (V,E) есть пара множеств, где V — множество вершин (узлов), E — множество дуг (ориентированных рёбер). Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v → w ведет от вершины v к вершине w, при этом вершина w смежная с вершиной v.