Задание 4. Формула называется выполнимой, если существует такой набор высказываний, который обращает эту формулу в истинное высказывание (есть хотя бы одно значение 1 в

Задание 4

Чтобы составить наглядное представление о графе, достаточно вообразить некоторое множество точек плоскости или пространства и множество отрезков, соединяющих все или некоторые из этих точек. Точки множества называют вершинами, а отрезки, их соединяющие,— дугами, если указано, какая вершина является начальной, и ребрами, если ориентация не указана. Два ребра, связывающие одну и ту же пару вершин, называются кратными. Ребро, связывающее вершину саму с собой, называется петлей.

Граф, состоящий из дуг, называют ориентированным (орграфом), а образованный ребрами — неориентированным.

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

Формально граф определяется заданием двух множеств и , где — множество вершин; — множество дуг (ребер).

При большом числе элементов рисунок графа теряет наглядность. В таком случае граф целесообразно задать матричным способом.

Матрица смежности вершин орграфа — это квадратная матрица -го порядка ( — число вершин). Строки и столбцы матрицы соответствуют вершинам графа. Элементы матрицы равны числу дуг, направленных из -й вершины в -ю. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0, либо 1. Если орграф состоит из однократных дуг, то элементы матрицы равны либо 0, либо 1.

В случае неориентированного графа ему вместе с ребром принадлежит и ребро , поэтому матрица будет симметрической. Справедливо и обратное заключение: любой симметрической матрице с целыми неотрицательными элементами можно поставить в соответствие граф.

Матрица смежности дуг орграфа — это квадратная матрица -го порядка ( — число дуг). Строки и столбцы матрицы соответствуют дугам графа. Элементы равны 1, если дуга непосредственно предшествует дуге , и 0 в остальных случаях.

Матрицей смежности ребер неориентированного графа является матрица -го порядка ( — число ребер) с элементами равными 1, если ребра и имеют общую вершину, и 0 в остальных случаях.

Матрица инцидентности орграфа — это прямоугольная матрица размерности , строки которой соответствуют вершинам, а столбцы — дугам орграфа. Элементы равны 1, если дуга исходит из -й вершины; , если дуга заходит в -ю вершину; 0, если дуга не инцидентна -й вершине. В случае неориентированного графа элементами матрицы будут лишь 1 и 0.

Пример.