Дискретная математика
141 помощью перестановки строк и столбцов матрицы инциденций. Теперь можно утверждать следующее. Два графа изоморфны тогда и только тогда, если они имеют одни и те же матрицы инциденций с точностью до перестановок строк и столбцов. Теорема 5.9. Ранг матрицы инциденций /з-компонентного графа с п вершинами равен п-р при условии, что арифметичесхсие операции производятся по модулю 2. Доказательство. Добьемся, чтобы матрица инциденций стала блочной. Пусть т - число вершин, принадлежащих компоненте связности О/ и ей соответствует блок А] матрицы инциденций А. Покажем, что ранг А] равен п,-1. Для ранга имеем: г < П] -1, так как сумма (по модулю 2) всех столбцов Л ; равна нулю, следовательно, если л/ -1 первых столбцов A j прибавить к последней, то получим столбец, состоящий из нулей. Так как ранг матрицы н е меняется при элементарных преобразованиях (сложение столбцов), ранг новой матрицы, имеющей столбец только из нулей, не может превосходить П; -1. Сумма любых rij -1 или меньшего числа столбцов А] должна иметь некоторый ненулевой элемент. Если все элементы равны нулю, тогда исходные строгш образуют подматрицу, соответствующую компоненте связности графа, так как ни одна из вершин, соответствующих этим столбцам, не связана ребром ни с одной из вершин, не принадлежащи^с рассматриваемому подмножеству. Это противоречит тому, что G; - максимальный связный подграф, и доказывает, что ранг G/ равен л/ -1, так как каждое множество nj-l столбцов независимо. Аналогично для каждого i ранг А, равен п, -1, тогда ранг блочной р матрицы, как известно, равен X (''i -1 )= "-Р- Что и требовалось доказать. 1=/ Матрица инциденций орграфа с п вершинами и т дугами это пхт матрица, элемент которой равен: ^ если из г-й вершины исходит j-я дуга, -1, если в г'-ю вершину входит j-я дуга, а у - если /-Я вершина не инцидентна j-й дуге. Пусть дан орграф, изображённый на рис. 5.19. Тогда его матр5 инциденций А имеет вид:
Made with FlippingBook
RkJQdWJsaXNoZXIy MTY0OTYy