Cтраница 1
Матрица инциденций графа представляет собой двумерную таблицу, каждой строке которой взаимно однозначно соответствует дуга графа, столбцу - вершина, и элемент равен 1, если соответствующая ему дуга положительно инцидентна соответствующей вершине, - 1, если отрицательно инцидентна, и 0 при отсутствии инииденции. [1]
Если матрица инциденций графа является абсолютно унимоду-лярной, то экстремальная задача на таком графе сводится к задаче линейного программирования, что в конечном итоге обеспечивает построение простых и эффективных алгоритмов поиска экстремума. Кроме того, для таких задач справедливы теоремы двойственности линейного программирования, следствием которых являются многие важные комбинаторные теоремы. [2]
Если из матрицы инциденций графа его цикломатические матрицы получаются без особого труда ( см., например, [4], гл. Аусландера и Трента [73, 74], где дается теоретически удовлетворительное, но практически мало эффективное ее решение. Полноценное решение этой задачи, по существу исключающее необходимость полного перебора всевозможных случаев, удалось Лефгрену [32]; сам автор применяет свой метод к проблеме реализации булевых форм неизбыточными схемами, но ясно, что он не менее эффективен и в отношении теории электрических цепей, в которой рассматриваемая задача возникла впервые; переводчица Б. Ю. Пильчак снабдила статью большим количеством добавлений. Казахара, Тезука, Линг Шан Тонг и Китаха-ши [149] предлагают два метода получения всех деревьев графа, исходя из одного дерева. Сэшу [194] приводит условия того, что матрица с элементами 0 1 и - 1 является матрицей разреза некоторого ориентированного графа. [3]
Ьц ] - матрица инциденций графа О и 7 - 1 или 0 в зависимости от того, входит ли ребро а - в паросочетание. [4]
С, - матрица инциденций шпиндельного графа G, у которой вычеркнута одна строка; С; - транспонированная матрица С. [5]
Второе правило, позволяющее построить матрицу инциденций графа, предполагает, кроме нумерации п вершин, независимую нумерацию т его ребер. Тогда элементы Ьц этой матрицы, имеющей п строк и т столбцов, будут равны единице, если вершина vt и ребро - X) инцидентны и равны нулю в противном случае. [6]
Тогда построение дерева осуществимо с помощью ЭВМ по матрице инциденций графа. [7]
LJ и вершины А, матрица Е - матрицей инциденции графа С. Переход к матрице инциденции графа позволяет перевести на аналитич. В нек-рых случаях, наоборот, свойства матрицы инциденции оказывается удобным формулировать в терминах связанного с ней графа. [8]
Рассмотрим два алгоритма поиска деревьев СТГ, использующие свойства матрицы инциденций графа ( алгоритм АГД-I) и структурного числа графа ( алгоритм АГД-II), которые позволяют формализовать процедуру выбора специального дерева СТГ, обладающего свойством минимального перекрывания. [9]
Сопоставим каждому ребру из G соответствующую ему строку в матрице инциденций графа G, рассматривая ее как вектор, каждая компонента которого равна нулю или единице. При этом, если подмножество ребер из G образует цикл, то сумма ( по модулю два) соответствующих этим ребрам векторов равна нулю. Следовательно, циклический матроид М ( G) графа G является бинарным. Для коциклического матроида доказательство аналогично. [10]
Следующая теорема связывает матрицу смежностей реберного графа графа G и матрицу инциденций графа G. Обозначим через ВТ матрицу, транспонированную к матрице В. [11]
Матрица системы уравнений ( VI-2) для кольца без ответвлений в точности совпадает с 1 - й матрицей инциденций графа. [12]
LJ и вершины А, матрица Е - матрицей инциденции графа С. Переход к матрице инциденции графа позволяет перевести на аналитич. В нек-рых случаях, наоборот, свойства матрицы инциденции оказывается удобным формулировать в терминах связанного с ней графа. [13]
Нетрудно показать, что если G - граф, то его циклический матроид M ( G) является бинарным. Чтобы убедиться в этом, сопоставим каждому ребру из G соответствующую ему строку в матрице инциденций графа G ( упр. [14]
Ввиду явной нецелесообразности канонической поатомной записи сложных органических молекул все известные поатомные системы кодирования являются неканоничными. Поатомные коды структурных формул, как правило, представляют собой ту или иную модификацию ( 0 1) матрицы инциденций графа. Приводим изображение некоторого графа и соответствующей ему матрицы инциденций. [15]