Содержание
- 2. ОПЕРАЦИИ НАД ГРАФАМИ Рис. 10.16
- 3. ОПЕРАЦИИ НАД ГРАФАМИ 4. Произведение двух графов Gl и G2 есть граф G, для которого x1•
- 4. ОПЕРАЦИИ НАД ГРАФАМИ 5. Стягивание ребра означает отождествление смежных вершин (рис. 10.18). Рис. 10.18
- 5. ОПЕРАЦИИ НАД ГРАФАМИ 6. Расщепление вершин — это операция двойственная стягиванию ребра (рис. 10.19) Рис. 10.19
- 6. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ Графы можно задавать с помощью матриц. Построим некоторые из них. Матрицей смежности вершин
- 7. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ Для орграфа (рис. 10.20) построить матрицу смежности A(G). Рис. 10.20
- 8. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ
- 9. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ Матрицей инциденций B(G) = {bik] орграфа G = (X,U) называется прямоугольная матрица размерности
- 10. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ В матрице инциденций для неографа при ее построении элементы -1 следует заменить на
- 11. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ Матрицей пропускных способностей дуг C(G) = {cik} графа G называется квадратная матрица размерности
- 12. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ Матрицей достижимостей D(G) = {djk} графа G называется квадратная матрица размерности n х
- 13. МАТРИЧНЫЕ ПРЕДСТАВЛЕНИЯ ГРАФОВ
- 14. СВЯЗНОСТЬ ГРАФОВ И КОМПОНЕНТЫ СВЯЗНОСТИ Граф G(X,U), в котором все вершины соединены простой цепью называется связным.
- 15. СВЯЗНОСТЬ ГРАФОВ И КОМПОНЕНТЫ СВЯЗНОСТИ На рис. 10.22, а граф имеет две компоненты связности, на рис.
- 16. СВЯЗНОСТЬ ГРАФОВ И КОМПОНЕНТЫ СВЯЗНОСТИ Число компонент связности графа G обозначается k(G). Граф G является связным,
- 17. СВЯЗНОСТЬ ГРАФОВ И КОМПОНЕНТЫ СВЯЗНОСТИ Вершина графа G называется точкой сочленения, если ее удаление увеличивает число
- 18. СВЯЗНОСТЬ ГРАФОВ И КОМПОНЕНТЫ СВЯЗНОСТИ Рис. 10.23 Теорема. Граф G = (X,U) связен тогда и только
- 19. СВЯЗНОСТЬ ГРАФОВ И КОМПОНЕНТЫ СВЯЗНОСТИ Орграф G1 называется сильно связным графом или сильным, если для любых
- 20. СВЯЗНОСТЬ ГРАФОВ И КОМПОНЕНТЫ СВЯЗНОСТИ Орграф G3 называется слабосвязным или слабым, если для двух любых вершин
- 21. СВЯЗНОСТЬ ГРАФОВ И КОМПОНЕНТЫ СВЯЗНОСТИ Длиной маршрута называется количество ребер в нем (с повторениями). Обозначается ׀М׀
- 22. СВЯЗНОСТЬ ГРАФОВ И КОМПОНЕНТЫ СВЯЗНОСТИ На рис. 10.28 указаны эксцентриситеты вершин и центры двух графов G1
- 23. Циклы Эйлера и Гамельтона Задача Эйлера (о кенигсбергских мостах) заключается в нахождении маршрута путем обхода семи
- 24. Циклы Эйлера и Гамельтона Если в графе имеется цикл, содержащий все ребра графа по одному разу,
- 25. Циклы Эйлера и Гамельтона Эйлеров цикл содержит не только все ребра (по одному разу) графа, но
- 26. Циклы Эйлера и Гамельтона Теорема Эйлера. Если граф G = (X,U) связан и нетривиален, то следующие
- 27. Циклы Эйлера и Гамельтона Название гамельтоновых циклов произошло от задачи о кругосветном путешествии, сформированной У. Гамельтоном:
- 28. Циклы Эйлера и Гамельтона Рис. 10.31 Если граф имеет простейший цикл, содержащий все вершины графа по
- 29. Циклы Эйлера и Гамельтона Теорема. Если в графе G = (Х,U) с n вершинами степень каждой
- 31. Скачать презентацию