математика - задачка
в связи вот с этим разговором вспомнилась одна задачка, с которой я столкнулась лет десять назад. Тогда она была мне актуальна по рабочим делам, сейчас интерес уже чисто абстрактный, но почему-то все равно никто не хочет на эту тему поговорить. ;-)
Но тут много френдов-математиков, вдруг у кого-то будут идеи?
Представим себе графы, обладающие следующими свойствами:
- связные обыкновенные графы (т.е. без кратных ребер и петель) с конечным числом вершин;
- все вершины топологически эквивалентны - принадлежат одной орбите группы автоморфизмов;
- графы планарные, т.е., согласно теореме Куратовского, не имеют подграфов, гомеоморфных K3,3 или K5;
- степень всех вершин - либо 3, либо 4.
Какие это могут быть графы?
Сразу приходят в голову графы, "соответствующие" следующим выпуклым многогранникам:
- призмы (степень вершин 3) и антипризмы (степень 4), где основания имеют любое число вершин;
- платоновы тела (куб считается среди призм, октаэдр - среди антипризм, плюс еще тетраэдр и додекаэдр);
- архимедовы тела.
А еще что-нибудь есть? Особенно интересно про степень 3.
С одной стороны, других вершинно-транзитивных выпуклых многогранников вроде и нет. С другой стороны - а почему бы не существовать вершинно-транзитивным планарным графам, просто не имеющим столь же симметричных геометрических реализаций?
Вроде когда-то где-то была статья на смежную тему, но найти текст мне не удалось - да если бы и удалось, еще вопрос, смогла бы я его понять или нет.
Но тут много френдов-математиков, вдруг у кого-то будут идеи?
Представим себе графы, обладающие следующими свойствами:
- связные обыкновенные графы (т.е. без кратных ребер и петель) с конечным числом вершин;
- все вершины топологически эквивалентны - принадлежат одной орбите группы автоморфизмов;
- графы планарные, т.е., согласно теореме Куратовского, не имеют подграфов, гомеоморфных K3,3 или K5;
- степень всех вершин - либо 3, либо 4.
Какие это могут быть графы?
Сразу приходят в голову графы, "соответствующие" следующим выпуклым многогранникам:
- призмы (степень вершин 3) и антипризмы (степень 4), где основания имеют любое число вершин;
- платоновы тела (куб считается среди призм, октаэдр - среди антипризм, плюс еще тетраэдр и додекаэдр);
- архимедовы тела.
А еще что-нибудь есть? Особенно интересно про степень 3.
С одной стороны, других вершинно-транзитивных выпуклых многогранников вроде и нет. С другой стороны - а почему бы не существовать вершинно-транзитивным планарным графам, просто не имеющим столь же симметричных геометрических реализаций?
Вроде когда-то где-то была статья на смежную тему, но найти текст мне не удалось - да если бы и удалось, еще вопрос, смогла бы я его понять или нет.