12
.pdf
Нахождение остова наименьшего веса
Представление графов в Rd
Определение. Представлением графа G = (V ; E) в пространстве Rd , d = 1; 2; 3; : : : , называется изоморфный ему граф G0 = (V 0; E0) такой, что вершины из V 0 точки пространства Rd , а ребра из E0 непересекающиеся дуги.
Нахождение остова наименьшего веса
Представление графов в Rd
Определение. Представлением графа G = (V ; E) в пространстве Rd , d = 1; 2; 3; : : : , называется изоморфный ему граф G0 = (V 0; E0) такой, что вершины из V 0 точки пространства Rd , а ребра из E0 непересекающиеся дуги.
Теорема. Каждый граф имеет представление в R3.
Нахождение остова наименьшего веса
Представление графов в Rd
Определение. Представлением графа G = (V ; E) в пространстве Rd , d = 1; 2; 3; : : : , называется изоморфный ему граф G0 = (V 0; E0) такой, что вершины из V 0 точки пространства Rd , а ребра из E0 непересекающиеся дуги.
Теорема. Каждый граф имеет представление в R3.
Доказательство. Фиксируем прямую `,
Нахождение остова наименьшего веса
Представление графов в Rd
Определение. Представлением графа G = (V ; E) в пространстве Rd , d = 1; 2; 3; : : : , называется изоморфный ему граф G0 = (V 0; E0) такой, что вершины из V 0 точки пространства Rd , а ребра из E0 непересекающиеся дуги.
Теорема. Каждый граф имеет представление в R3.
Доказательство. Фиксируем прямую `, она лежит в бесконечном множестве плоскостей в R3.
Нахождение остова наименьшего веса
Представление графов в Rd
Определение. Представлением графа G = (V ; E) в пространстве Rd , d = 1; 2; 3; : : : , называется изоморфный ему граф G0 = (V 0; E0) такой, что вершины из V 0 точки пространства Rd , а ребра из E0 непересекающиеся дуги.
Теорема. Каждый граф имеет представление в R3.
Доказательство. Фиксируем прямую `, она лежит в бесконечном множестве плоскостей в R3. Пусть V 0 множество точек на `.
Нахождение остова наименьшего веса
Представление графов в Rd
Определение. Представлением графа G = (V ; E) в пространстве Rd , d = 1; 2; 3; : : : , называется изоморфный ему граф G0 = (V 0; E0) такой, что вершины из V 0 точки пространства Rd , а ребра из E0 непересекающиеся дуги.
Теорема. Каждый граф имеет представление в R3.
Доказательство. Фиксируем прямую `, она лежит в бесконечном множестве плоскостей в R3. Пусть V 0 множество точек на `. Каждому ребру ставим в однозначное соответсвие некоторую плоскость содержащую `.
Нахождение остова наименьшего веса
Представление графов в Rd
Определение. Представлением графа G = (V ; E) в пространстве Rd , d = 1; 2; 3; : : : , называется изоморфный ему граф G0 = (V 0; E0) такой, что вершины из V 0 точки пространства Rd , а ребра из E0 непересекающиеся дуги.
Теорема. Каждый граф имеет представление в R3.
Доказательство. Фиксируем прямую `, она лежит в бесконечном множестве плоскостей в R3. Пусть V 0 множество точек на `. Каждому ребру ставим в однозначное соответсвие некоторую плоскость содержащую `. Проводим каждую дугу из E0 в соотвествуещей плоскости.
Нахождение остова наименьшего веса
Плоские графы
Определение. Граф называется плоским, если он представим в пространстве R2.
Нахождение остова наименьшего веса
Плоские графы
Определение. Граф называется плоским, если он представим в пространстве R2.
Теорема. Каждое дерево (а следовательно каждый лес) является плоским графом.
Нахождение остова наименьшего веса
Плоские графы
Определение. Граф называется плоским, если он представим в пространстве R2.
Теорема. Каждое дерево (а следовательно каждый лес) является плоским графом.
Определение. Гранью в плоском представлении называется часть пространства R2; отделенная дугами этого представления.