Задачи раскраски графов. Вершинная раскраска
Отметим в заключение, что стягивая любое ребро планарного графа, вновь получим планарный граф. Если же дан непланарный граф, то стянув одно или несколько ребер можно получить планарный граф. Хроматическо е числ о графа. Раскраска вершин графа G называется правильной, если любые две смежные вершины окрашены в разные цвета. Правильная раскраска графа G , при которой использовано k различных цветов, называется k-раскраской , а граф G , для которого существует k -раскраска, называется k -раскрашиваемым.
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны. Понятие «граф» связано с понятием «графический», «графика». Действительно, графовые модели имеют простую и понятную графическую интерпретацию, позволяющую с их помощью образно представить самые разные объекты, в то же время оставаясь в рамках строгих математических моделей. Первой работой теории графов как математической дисциплины считают статью Эйлера г. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз.
Мы предполагаем, что вам понравилась эта презентация. Чтобы скачать ее, порекомендуйте, пожалуйста, эту презентацию своим друзьям в любой соц. Кнопочки находятся чуть ниже. Презентация была опубликована 10 лет назад пользователем Жанна Саушкина. Теорема Брукса Если граф G не является полным графом или нечетным циклом, то G.
