|
Народ, помогите пожалуйста решить задачи по теории графов. Может какие-нибудь из нижеприведенных вы знаете как решать
1)G-внешнепланарный граф, доказать что существует вершина степени <= 2
2) G - не 4-ч связнаю триангуляция, доказать что существует разделяющий трегольник
3) G - критический, m(число ребер) <= 2n-4, n -число вершин
4)Привести пример графа: кубический, 3-х связный, двудольный, негамильтонов
5)G-плоский, гамильтонов, доказать что его грани можно раскрасит в 4 цвета
6)e(G) = e(G^3) описать такие графы, e(G) -число вершинной независимости в графе
|
12.12.2006, 23:51 