Задание по теории графов.

[stedent076]

Дано:
Нарисовать граф $K(2;3)$ и определить, является ли он планарным. Если да, найти число его граней. Является ли он Эйлеровым графом?
Мое решение:
1)Данный граф имеет две вершины и три ребра. Согласно определению планарного графа, таковым является граф, который можно изобразить на плоскости без пересечения ребер во внутренних точках. Поэтому, предъявляя соответствующее построение, мы сможем точно сказать, что он планарный. Извините, картинку прикрепить не могу, так как набираю текст с телефона, но постараюсь описать построение:
1.1)Отмечаем две точки на плоскости.
1.2)Проводим отрезок, соединяющий их.
1.3)Замчаем, что к какой-либо из точек будет прилегать два ребра, так как количество последних на единицу больше количества вершин
2)Легко заметить, что допустимо построение, в котором каждая вершина имеет четную степень.
3)Граф связен и для каждой вершины графа её полустепень захода равна её полустепени исхода, то есть в вершину входит столько же ребер, сколько из неё и выходит, а значит существует Эйлеров цикл и Эйлеров путь.
4)По теореме Эйлера, количество граней равно трем.
Ответ: Граф планарен, Эйлеров, имеет три грани.

[provincialka]

Вы неправильно поняли обозначение. Графа с 2 вершинами и 3 ребрами не бывает. Ва задан полный двудольный грсф с 2 и 3 вершинами в долях.

[Pulseofmalstrem]

stedent076
Для проверки планарности можно использовать формулу Эйлера или теорему Понтрягина-Куратовского (это даст моментальный ответ), для проверки эйлеровости графа разумно использовать критерий эйлерова графа, который говорит о том, что все вершины должны иметь четные степени.

[stedent076]

provincialka
Если учесть ваши замечание, то граф имеет следующий вид:


(вставить как картинку не получилось, извиняйте))

Lia: Разрешение выбирайте подходящее. Максимальная ширина, как Вы, думаю, заметили при попытке вставки, 800 px.

[provincialka]

Да. Граф такой. Планарность можно проверить с помощью соотв. теоремы. Или непосредственно, если удастся расположить вершины подходящим способом (удастся!).

[stedent076]

provincialka
А так можно?

Pulseofmalstrem в сообщении #1117206 писал(а):

Для проверки планарности можно использовать формулу Эйлера или теорему Понтрягина-Куратовского (это даст моментальный ответ), для проверки эйлеровости графа разумно использовать критерий эйлерова графа, который говорит о том, что все вершины должны иметь четные степени.

[provincialka]

stedent076
Про Эйлеров-- совершенно верно. Планарность же видна "невооруженным взглядом". Просто пошевелите вершины.