Заочная физико-техническая школа Московского физико-технического института         
Задачи и решения
  Вернуться к сообщениям форума  |  Ответить на сообщение 
Математика 10 класс задание 4 и теорема Эйлера для графа на сфере
Сообщение прислал(а): Гега (CELERON)
Дата написания: 8 февраля 2004г. 03:35:51

Тут я сам интересовался как эту задачу решить
можно...Задача такая:
в 8-угольнике проведены все диагонали , при этом никакие
3 диагонали не пересекаются в одной точке.Найти количество
частей , на которые разделится 8-угольник.

Эта задача решается с помощью теоремы Эйлера для графа на
сфере. Теорема интересная , очень полезная . Звучит она так:
( Рассматривается произвольный граф на сфере. )
Для любого графа верно , что
В - Р + Г - К = 1
где В - количество вершин
Р - количество рёбер
Г - количество граней
К - количество компонент связности
Компонентой связности называют такой подграф ,
в котором от каждой вершины можно добраться до любой
другой.

(
для многогранника , очевидно К = 1 и это теорема
превращаеся в "школьную" теорему Эйлера В - Р + Г = 2

замечание: в теореме говорится о графе на сфере ,
а у нас просто многогранник . Чтобы превратить
многоранник в граф на сфере , достаточно внутрь многогранника
поместить сферу ( а вот это всегда можно сделать , нужно
только внимательно изучить что такое многогранник )
и спроецировать рёбра и вершины многогранника на сферу
)

Доказательство этой теоремы есть в каком-то из квантов .
Номер не вспомню , мы этот номер как-то семинарили в школе
( очень классный способ работы кстати - народ поочерёдно
готовит материал , потом рассказывает остальным . )
Там ещё много интересного на эту тему было ( ещё теорема Коши
о "незгибаемости" многогранников , какие-то следствия из
теоремы Эйлера ).

Вот. Могу привести идею доказательства ( так как самого его
у меня нет , но идею я хорошо помню ( записал когда
семинарили ) )

Доказательство:

1. Рассмотрим сначал граф без ребёр ( эдакое "звёздное небо" )
Для этого графа очевидно верно , что
Р = 0 , Г = 1 ( повторю , что рассматривается граф
на сфере , и что у него всегда есть
одна грань - сама сфера .
Например: если бы граф состоял просто
из квадратика , то у него было бы
две грани - одна "внутренняя" часть
квадратика , и вторая - "внешняя" часть
, [ всё то что не внутренняя =) ] )
и также В = К .
( Каждая вершина по отдельнотси является компонентой
связности , и так как ребёр у нас нет , то это равенство
становится весьма очевидным . )

Итого имеем В - Р + Г - К = ( В - К ) - Р + Г = 0 - 0 + 1 = 1

То есть для графа "звёздное небо" Теорема Эйлера верна.

2.
Теперь покажем , что любой граф можно свести к графу
"звёздное небо" удалением рёбер , и что при этом
величина А = В - Р + Г - К остаётся постоянной

1) Рассмотрим случай , если в графе есть ребро
со "свободным концом" , то есть если есть
такая вершина , из которой выходит только одно ребро.

Удалим это ребро , и посмотрим как изменятся
величины В , Р , Г , К .
В` = В ( количество вершин , очевидно не поменялось
прим.: ребро удаляется без вершин )
Р` = Р - 1 ( одно ребро удалили )
Г` = Г ( количество граней также не изменилось ,
это следует из "вида" ребра которое мы удаляем )
К` = К + 1 ( добавилась одна вершина => добавилась
компонента связности )

итого
В` - Р` + Г` - К` = В - ( Р - 1 ) + Г - ( К + 1 ) =
В - Р + 1 - К - 1 = В - Р + Г - К = А .
величина А остаётся постоянной

2) Если в графе не осталось рёбер выше рассмотренного
вида , то либо в нём более нет рёбер ,
либо из каждой вершины выходит минимум по два ребра.
Рассмотрим второй случай.
Если из каждой вершины выходит минимум по два ребра ,
то существует замкнутый путь

 Математика 10 класс задание 4 и теорема Эйлера для графа на сфере (3246) - Гега (CELERON) [08.02.04 03:35]
 Забанят ведь...Срок еще не кончился! (2864) - Ирина (pier.botik.ru) [09.02.04 14:36]

Ответить на сообщение
При публикации вопросов, связанных с задачами, приводите, пожалуйста, ИХ УСЛОВИЯ.
Тема сообщения:
Ваше имя:
Ваш E-Mail:
Текст сообщения:
[Добавить формулу]
Сотрудник ЗФТШ:   
  

© 2002-2019, ЗФТШ МФТИ
    Пожелания вебмастеру
ЛЕКТОРИЙ | ПРОГРАММЫ ОБУЧЕНИЯ | МЕТОДИСТЫ | ШКОЛЬНИКАМ
Разработка 100ляров