Многочлен Татта — различия между версиями
(→Основные определения) |
|||
| Строка 11: | Строка 11: | ||
==Существование и единственность== | ==Существование и единственность== | ||
| − | {{Определение | + | {{Определение|definition= |
Пусть <tex> G = (V,E) </tex> - некоторый граф. Для множества <tex> A \subset E </tex> через <tex> G(A) </tex> будем обозначать граф <tex> (V, A) </tex>. Через <tex> с(G) </tex> будем обозначать '''число компонент связности''' графа <tex> G </tex>. '''Рангом''' множества <tex> A </tex> будем называть число <tex> \rho(A) = |V| - c(G(A)) </tex>. | Пусть <tex> G = (V,E) </tex> - некоторый граф. Для множества <tex> A \subset E </tex> через <tex> G(A) </tex> будем обозначать граф <tex> (V, A) </tex>. Через <tex> с(G) </tex> будем обозначать '''число компонент связности''' графа <tex> G </tex>. '''Рангом''' множества <tex> A </tex> будем называть число <tex> \rho(A) = |V| - c(G(A)) </tex>. | ||
}} | }} | ||
| − | {{ Замечание|statement= | + | {{Замечание|statement= |
Ранг множества <tex> А </tex> равен количеству рёбер в любом остовном лесе графа <tex> G(A) </tex>. (Под остовным лесом здесь понимается объединение остовных деревьев всех компонент связности, т.е. такой ациклический граф <tex> G(B) </tex>, что <tex> B \subset A </tex> и <tex> c(G(B)) = c(G(A)) </tex>). | Ранг множества <tex> А </tex> равен количеству рёбер в любом остовном лесе графа <tex> G(A) </tex>. (Под остовным лесом здесь понимается объединение остовных деревьев всех компонент связности, т.е. такой ациклический граф <tex> G(B) </tex>, что <tex> B \subset A </tex> и <tex> c(G(B)) = c(G(A)) </tex>). | ||
}} | }} | ||
Версия 16:06, 15 декабря 2013
Основные определения
| Определение: |
Рассмотрим граф , возможно петлями и кратными рёбрами. Определим многочлен Татта следующими рекурсивными соотношениями:
|
Разумеется, существование и единственность многочлена Татта ещё нужно доказать. Для того чтобы это сделать, покажем что многочлену Татта соответствует, так называемый, ранговый многочлен, который уже задаётся явной формулой.
Существование и единственность
| Определение: |
| Пусть - некоторый граф. Для множества через будем обозначать граф . Через будем обозначать число компонент связности графа . Рангом множества будем называть число . |
