В математике гомотопическая теорема Тутте , введенная Тутте ( 1958 ), обобщает концепцию «пути» от графов к матроидам и грубо заявляет, что замкнутые пути могут быть записаны как композиции элементарных замкнутых путей, так что в некотором смысле они гомотопен тривиальному замкнутому пути.
Заявление [ править ]
Матроид на множество Q задается классом непустых подмножеств M из Q , называемые схемы , таким образом, что ни один элемент М не содержит другой, и если Х и Y находятся в М , в X и Y , б является в X , но не в Y , то есть некоторые Z в М , содержащий Ь , но не и содержится в X ∪ Y .
Подмножества Q, которые являются объединениями схем, называются плоскими (это язык, использованный в исходной статье Тутта, однако в современном использовании плоские части матроида означают нечто иное). Элементы M называются 0-квартирами, минимальные непустые квартиры, которые не являются 0-квартирами, называются 1-квартирами, минимальные непустые квартиры, которые не являются 0-квартирами или 1-квартирами, называются 2-квартирами, и так на.
Путь конечная последовательность из 0-квартиры, что любые два последовательных элементов путей лежат в некоторой 1-квартире.
Элементарный путь является одним из вида ( X , Y , X ), или ( Х , Y , Z , X ) с X , Y , Z , лежащих в некоторой 2-квартире.
Два пути P и Q, такие, что последняя 0-плоскость P совпадает с первой 0-плоскостью Q, могут быть составлены очевидным образом, чтобы получить путь PQ .
Два пути называются гомотопическими, если один может быть получен из другого с помощью операций добавления или удаления элементарных путей внутри пути, другими словами, путем изменения пути PR на PQR или наоборот, где Q является элементарным.
Слабая форма теоремы о гомотопии Тутте утверждает, что любой замкнутый путь гомотопен тривиальному пути. Более сильная форма утверждает аналогичный результат для путей, не встречающихся с некоторыми «выпуклыми» подмножествами.
Ссылки [ править ]
- Tutte, Уильям Томас (1958), "Гомотопия теорема для матроидов я.", Труды Американского математического общества , 88 : 144-160, DOI : 10,2307 / 1993243 , ISSN 0002-9947 , JSTOR 1993243 , MR 0101526
- Tutte, Уильям Томас (1958), "Гомотопия теорема для матроидов II.", Труды Американского математического общества , 88 : 161-174, DOI : 10,2307 / 1993244 , ISSN 0002-9947 , JSTOR 1993244 , MR 0101526
- Тутт, У. Т. (1971), Введение в теорию матроидов , Современные аналитические и вычислительные методы в науке и математике, 37 , Нью-Йорк: American Elsevier Publishing Company, стр. 72–77, Zbl 0231.05027
- Белый Нил (1987), "Унимодулярные матроиды" , в белом, Нил (ред . ), Комбинаторной геометрии , энциклопедии математики и ее применения, 29 , Cambridge University Press , стр 40-52,. Дои : 10,1017 / CBO9781107325715 , ISBN 978-0-521-33339-9, Руководство по ремонту 0921064