Вопросы к коллоквиуму по теории графов

Вопросы к коллоквиуму по теории графов

Определение графа. Вершина инцидентная ребру. Смежные вершины. Смежные рёбра. Порядок графа. Полный граф . Вычислить число рёбер в полном графе . Изоморфные графы. Привести пример изоморфных графов. Объединение графов. Пересечение графов. Подграф. Индуцированный граф. Остовной подграф. Разность графов. Дополнение к графу Доказать, что в любом конечном графе существуют две вершины, имеющие одинаковую степень. Степень вершины. Минимальная и максимальная степени графа. Однородный граф. Средняя степень графа. Доказать, что число вершин нечётной степени в любом графе чётно. Путь. Длина пути. Независимые пути. пути. Цикл. Длина цикла. Обхват графа . Периметр графа. Хорда цикла. Доказать, что каждый граф содержит путь длины где — минимальная степень графа. Расстояние между вершинами графа. Диаметр графа . Доказать, что каждый граф содержащий цикл, удовлетворяет условию , где – обхват графа . Центральная в графе вершина. Радиус графа Доказать, что Доказать, что в графе радиуса не более с максимальной степенью не более имеется не более вершин. Доказать, что каждый маршрут между двумя вершинами содержит путь между этими вершинами. Связный граф. Компонента связности графа Разделяющее множество в -связный граф. Связность графа -рёберно связный граф. Рёберная связность графа Доказать, что если в графе порядка минимальная степень то граф связный. Доказать, что каждый граф средней степени не менее содержит - связный подграф. Эйлеров обход. Эйлеров граф. Доказать, что связный граф эйлеров тогда и только тогда, когда каждая его вершина имеет чётную степень. Доказать, что связный граф содержит маршрут с концами , проходящий через каждое ребро графа ровно один раз в том и только в том случае, когда – единственные вершины нечётной степени в графе. Гамильтонов цикл. Гамильтонов граф. Доказать, что каждый граф с вершинами и минимальной степенью имеет гамильтонов цикл. Ациклический граф. Дерево. Доказать эквивалентность следующих утверждений для графа – дерево. Любые две вершины в соединены единственным путём. – минимальный связный граф. – максимальный ациклический граф. Корень. Корневое дерево. Доказать, что каждый связный граф содержит нормальное остовное дерево, причём в качестве корня можно взять произвольную вершину графа. Доказать, что число различных помеченных деревьев порядка равно .