Содержание
- 2. ГРАФОМ G = (V, X) НАЗЫВАЕТСЯ ПАРА ДВУХ КОНЕЧНЫХ МНОЖЕСТВ: МНОЖЕСТВО ТОЧЕК И МНОЖЕСТВО ЛИНИЙ, СОЕДИНЯЮЩИХ
- 3. ТОЧКИ НАЗЫВАЮТСЯ ВЕРШИНАМИ, ИЛИ УЗЛАМИ, ГРАФА, ЛИНИИ – РЕБРАМИ ГРАФА. ПРИМЕРЫ ГРАФОВ
- 4. ЕСЛИ РЕБРО ГРАФА СОЕДИНЯЕТ ДВЕ ЕГО ВЕРШИНЫ, ТО ГОВОРЯТ, ЧТО ЭТО РЕБРО ИМ ИНЦИДЕНТНО. ДВЕ ВЕРШИНЫ
- 5. КРАТНЫЕ РЕБРА ЧИСЛО РЕБЕР, ИНЦИДЕНТНЫХ ВЕРШИНЕ A , НАЗЫВАЕТСЯ СТЕПЕНЬЮ ЭТОЙ ВЕРШИНЫ И ОБОЗНАЧАЕТСЯ deg(A). ЕСЛИ
- 6. deg(E) = 0 E – ИЗОЛИРОВАННАЯ ВЕРШИНА deg(G) = 1 deg(H) = 1 deg(E) = 1
- 7. ТЕОРЕМА В ГРАФЕ G(V, X) СУММА СТЕПЕНЕЙ ВСЕХ ЕГО ВЕРШИН – ЧИСЛО ЧЕТНОЕ, РАВНОЕ УДВОЕННОМУ ЧИСЛУ
- 8. ГРАФ НАЗЫВАЕТСЯ ПОЛНЫМ, ЕСЛИ ЛЮБЫЕ ДВЕ ЕГО РАЗЛИЧНЫЕ ВЕРШИНЫ СОЕДИНЕНЫ ОДНИМ И ТОЛЬКО ОДНИМ РЕБРОМ. ДОПОЛНЕНИЕМ
- 9. ОРГРАФ ДУГИ НАЧАЛО ДУГИ (A,B) КОНЕЦ ДУГИ (A,B) СТЕПЕНЬЮ ВХОДА (ВЫХОДА) ВЕРШИНЫ ОРГРАФА НАЗЫВАЕТСЯ ЧИСЛО РЕБЕР,
- 10. ПОСЛЕДОВАТЕЛЬНОСТЬ РЕБЕР НЕОРИЕНТИРОВАННОГО ГРАФА, В КОТОРОЙ ВТОРАЯ ВЕРШИНА ПРЕДЫДУЩЕГО РЕБРА СОВПАДАЕТ С ПЕРВОЙ ВЕРШИНОЙ СЛЕДУЮЩЕГО, НАЗЫВАЕТСЯ
- 11. ПУТЬ – УПОРЯДОЧЕННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ РЕБЕР ОРИЕНТИРОВАННОГО ГРАФА, В КОТОРОЙ КОНЕЦ ПРЕДЫДУЩЕГО РЕБРА СОВПАДАЕТ С НАЧАЛОМ СЛЕДУЮЩЕГО
- 12. ЦЕПЬ, ПУТЬ И ЦИКЛ В ГРАФЕ НАЗЫВАЮТСЯ ПРОСТЫМИ, ЕСЛИ ОНИ ПРОХОДЯТ ЧЕРЕЗ ЛЮБУЮ ИЗ ВЕРШИН НЕ
- 13. ГРАФ G НАЗЫВАЕТСЯ ПЛАНАРНЫМ(ПЛОСКИМ), ЕСЛИ СУЩЕСТВУЕТ ТАКОЙ ГРАФ G' , В ИЗОБРАЖЕНИИ КОТОРОГО НА ПЛОСКОСТИ РЕБРА
- 14. ЭЙЛЕРОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), КОТОРЫЙ СОДЕРЖИТ ВСЕ РЕБРА ГРАФА ТОЛЬКО ОДИН РАЗ. ГРАФ, ОБЛАДАЮЩИЙ ЭЙЛЕРОВЫМ
- 15. ГАМИЛЬТОНОВЫМ ПУТЕМ(ЦИКЛОМ) ГРАФА НАЗЫВАЕТСЯ ПУТЬ(ЦИКЛ), ПРОХОДЯЩИЙ ЧЕРЕЗ КАЖДУЮ ЕГО ВЕРШИНУ ТОЛЬКО ОДИН РАЗ. ГРАФ, СОДЕРЖАЩИЙ ГАМИЛЬТОНОВ
- 16. МАТРИЦЕЙ ИНЦИДЕНТНОСТИ ГРАФА G НАЗЫВАЮТ ТАБЛИЦУ B, СОСТОЯЩУЮ ИЗ n СТРОК(ВЕРШИНЫ) И m СТОЛБЦОВ(РЕБРА), В КОТОРОЙ:
- 17. МАТРИЦЕЙ СМЕЖНОСТИ ГРАФА G(V,X) БЕЗ КРАТНЫХ РЕБЕР НАЗЫВАЮТ КВАДРАТНУЮ МАТРИЦУ A ПОРЯДКА n, В КОТОРОЙ: ,
- 18. ЗАДАЙТЕ СЛЕДУЮЩИЙ ОРГРАФ ТАБЛИЦЕЙ ИНЦИДЕНТНОСТИ
- 19. ЗАДАЙТЕ СЛЕДУЮЩИЙ ГРАФ ТАБЛИЦЕЙ СМЕЖНОСТИ A B C D E u s t r
- 21. Скачать презентацию