Кіріспе
Граф теориясының математикалық саласында Кирхгоф теоремасы немесе Густав Кирхгоф атымен аталатын Кирхгофтың матрицалық ағаш теоремасы – графтың аралас ағаштарының саны туралы теорема. Бұл теорема графтың Лаплас матрицасының кіші матрицасының анықтамасы арқылы осы санды полиномдық уақытта есептеуге болатынын көрсетеді; нақтырақ айтқанда, сан Лаплас матрицасының кез келген кофакторына тең. Кирхгоф теоремасы – Кейли формуласының жалпыламасы, ол толық графтың аралас ағаштарының санын анықтайды. Кирхгоф теоремасы графтың Лаплас матрицасы түсінігіне сүйенеді, ол графтың градус матрицасынан (диагональдардағы төбелерінің градустары көрсетілген диагональдық матрица) және оның жабыстық матрицасынан (төбелері жабысқан жерлерде 1, ал қалғандарында 0 болатын (0,1) матрица) алынған айырмаға тең. n белгіленген төбелері бар берілген байланысқан G графигі үшін λ1, λ2, …, λn−1 оның Лаплас матрицасының нөлдік емес өзіндік мәндері болсын. Онда G графигінің аралас ағаштарының саны –
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the Laplacian matrix of the graph; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph. Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph, which is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a (0,1) matrix with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise). For a given connected graph G with n labeled vertices, let λ1, λ2, , λn−1 be the non zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is
Кирхгофтың 1847 жылғы түпнұсқалық мақаласының ағылшын тіліне аудармасын Дж. Б. О’Тул жасаған, ол 1958 жылы жарияланған.
Кейли формуласы
Кейли формуласы Кирхгофф теоремасынан ерекше жағдай ретінде шығады, себебі бір орында 1, екінші орында -1 және қалғандары 0 болатын кез келген вектор толық графтың Лаплас матрицасының өзіндік векторы болып табылады, ал сәйкес өзіндік мәні n-ге тең. Бұл векторлар n-1 өлшемді кеңістікті құрайды, сондықтан басқа нөлдік емес өзіндік мәндер жоқ. Балама ретінде, Кейли формуласы толық граф Kn-нің әртүрлі белгіленген ағаштарының санын есептейтіндіктен, біз Kn Лаплас матрицасының кез келген кофакторын есептеуіміз керек. Бұл жағдайда Лаплас матрицасының кез келген кофакторы nn-2-ге тең, бұл Кейли формуласы болып табылады.
Any cofactor of the above matrix is nn−2, which is Cayley's formula.
Қашықтықтағы ағаштардың нақты санағы
Кирхгоф теоремасын Лаплас матрицасының анықтамасын өзгерту арқылы күшейтуге болады. Әр төбеден шығатын қабырғаларды санаудың немесе төбелер жұбын байланыстырудың орнына, әр қабырғаны белгісіз деп белгілеңіз. Модификацияланған Лаплас матрицасының (i, j)-шы елемі i және j-шы төбелер арасындағы қабырғаларға сәйкес келетін белгісіздердің қосындысына тең болсын, егер i ≠ j болса, ал i = j болса, i-шы төбеден шығатын қабырғаларға сәйкес келетін барлық белгісіздердің теріс қосындысына тең болсын. Кез келген қатар мен бағанды жою арқылы модификацияланған Лаплас матрицасының анықтамасы (алғашқы Лаплас матрицасынан жайылған ағаштар санын табуға ұқсас) – бұл графтың қабырғаларына сәйкес келетін белгісіздердегі гомогенді полином (Кирхгоф полиномі) болады. Мүшелерді жинап, барлық мүмкін қысқартуларды жасағаннан кейін, алынған өрнектегі әрбір мономиал сол мономиалда пайда болатын белгісіздерге сәйкес келетін қабырғалардан тұратын жайылған ағашты көрсетеді. Осылайша, анықтаманы есептеу арқылы графтың барлық жайылған ағаштарын нақты санауға болады. Теореманың осы нұсқасының дәлелі үшін Bollobás (1998) еңбегіне қараңыз.
Матроидтар
Графиктің жайылған ағаштары графикалық матроидтың негізін құрайды, сондықтан Кирхгоф теоремасы графикалық матроидтағы негіздер санын есептеуге арналған формула ұсынады. Осы әдіс графикалық матроидтардың обобщениесі болып табылатын реттелген матроидтардағы негіздер санын санау үшін де қолданылуы мүмкін.