Читать реферат по информатике, вычислительной технике, телекоммуникациям: "Применение теории графов в информатике 2" Страница 5
(Назад)
(Cкачать работу)поводу доказательства этой теоремы сделаем одно замечание. Эта теорема известна, в основном, как вывод английского математика А. Кэли (1821—1895). Графы-деревья издавна привлекали внимание ученых. Се годня двоичные деревья используются не только ма тематиками, а и биологами, химиками, физиками и инженерами (подробнее об этом – в параграфе 6).
Теорема 10. Полный граф с пятью верши нами не является плоским.
Доказательство. Воспользуемся формулой Эйлера: В-Р+Г=2, где В — число вершин плоского графа, Р — число его ре бер, Г — число граней. Формула Эйлера справедлива для плоских связных графов, в которых ни один из многоугольников не лежит внутри другого.
Эту формулу можно доказать методом математиче ской индукции. Это доказательство мы опускаем. За метим только, что формула справедлива и для пространственных многогранников. Пусть все пять вершин графа соединены друг с дру гом. Замечаем, что на графе нет ни одной грани, ограниченной только двумя ребрами. Если че рез φ1 обозначить число таких граней, то φ2=0. Далее рассуждаем от противного, а именно: пред положим, что исследуемый граф плоский. Это значит, что для него верна формула Эйлера. Число вершин в данном графе В=5, число ребер Р=10, тогда число граней Г=2-В+Р=2-5+10=7.
Это число можно представить в виде суммы: Г=φ1+φ2+φ3+…, где φ3 – число граней, ограниченных тремя ребрами, φ4 — число граней, ограниченных че тырьмя ребрами и т. д.
С другой стороны, каждое ребро является границей двух граней, а поэтому число граней равно 2Р, в то же время 2Р=20=3φ3+4φ4+... . Умножив равенство Г=7=φ3+ φ4 + φ5 + … на три, получим ЗГ=21=3( φ3 + φ4 + φ5 + …).
Ясно, что (3φ3+3φ4+3φ5+…) < (3φ3+4φ4+ 5φ5+…) или 3Г
Похожие работы
Интересная статья: Основы написания курсовой работы