Определение. Пусть G - ориентированный граф. Пусть Mc - квадратная матрица, строки и столбцы которой обозначены вершинами ориентированного графа G.
Элемент i-ой строки и j-гo столбца матрицы Mc, обозначаемый cij, равен единице, если имеется ребро из i-ой вершины в j-ую вершину, и равен нулю в противном случае. Матрица Mc называется матрицей смежности графа G.
Замечание. Для сокращения записи обозначения строк и столбцов в матрицах смежности можно опускать, но рекомендуется их оставлять, особенно в матрицах больших размерностей.
Говоря о свойствах матрицы смежности ориентированного графа, необходимо отметить, что в отличие от матриц смежности неориентированного графа, она не является симметричной, поскольку наличие ориентированного ребра из i-ой вершины в j-ую вершину не гарантирует наличие ориентированного ребра из j-ой вершины в i-ую вершину. Также отметим, что число единиц в строке матрицы смежности равно степени выхода соответствующей вершины, а число единиц в столбцах определяет степень входа. Сумма всех единиц в матрице смежности ориентированного графа равна числу ориентированных рёбер этого графа.
Пример 1. Рассмотрим ориентированный граф G1, который состоит из множества вершин V(G1), содержащего 6 элементов, и множества рёбер E(G1), содержащего 6 элементов: V(G1) = {a, b, c, d, e, f}, E(G1) = {(a, b), (a, c), (b, d), (c, d), (e, c), (f, d)}. Визуальное представление ориентированного графа G1:
Определим для ориентированного графа G1 матрицу смежности.
Решение. Ориентированный граф G1 состоит из 6 вершин, поэтому его матрица смежности имеет размерность 6 на 6:
Полезно рядом с матрицей смежности указывать также степени (полустепени) вершин, тогда матрица смежности для ориентированного графа G1 будет иметь вид:
Пример 2. Рассмотрим ориентированный граф G2, который состоит из множества вершин V(G2), содержащего 6 элементов, и множества рёбер E(G2), содержащего 5 элементов: V(G2) = {a, b, c, d, e, f}, E(G2) = {(a, c), (b, e), (c, d), (d, e), (f, d)}. Визуальное представление ориентированного графа G2:
Определим для ориентированного графа G2 матрицу смежности.
Решение. Ориентированный граф G2 состоит из 6 вершин, поэтому его матрица смежности также имеет размерность 6 на 6:
Также представим ориентированный граф G2 матрицей смежности со степенями (полустепенями) вершин:
Определение. Пусть G - ориентированный граф. Пусть Mи – матрица, строки которой обозначены вершинами графа, а столбцы - рёбрами графа. Элемент i-ой строки и j-гo столбца матрицы Mи, обозначаемый Mij, равен единице, если i-ая вершина является начальной вершиной ориентированного ребра (i, j); равен минус единице, если i-ая вершина является конечной вершиной ориентированного ребра (i, j); и равен нулю в противных случаях. Построенная таким образом матрица Mи называется матрицей инцидентности графа G.
Пример 3. Для ориентированных графов G1и G2, показанных на рис. выше, определим матрицы инцидентности.
Решение. Ориентированный граф G1 состоит из 6 вершин и 6 рёбер, поэтому его матрица инцидентности имеет размерность 6 на 6:
Ориентированный граф G2 состоит из 6 вершин и 5 рёбер, поэтому его матрица инцидентности имеет размерность 6 на 5:
Упражнение. Для следующих ориентированных графов определите и запишите матрицу смежности и матрицу инцидентности: