Содержание
- 2. Базовые понятия: множество граф бинарное отношение смежность инцидентность цикл матрица Термины Ключевые слова: матрица смежностей матрица
- 3. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. С. 25-27. Харари Ф. Теория графов: Пер.
- 4. Основные принципы теории графов используются при построении математической модели для проектирования и анализа сетей ЭВМ Наиболее
- 5. Базовые сетевые топологии типа «кольцо», «звезда», «шина» и соответствующие им графы Актуальность и практическая направленность. 2
- 6. Матрица смежностей − двумерная таблица C=||cij|| размера n×n, где n − число вершин, элемент которой определяется
- 7. Для неориентированного графа матрица смежностей является симметричной Для ориентированного свойство симметрии не обязательно. Элемент матрицы определяется
- 8. Матрица инциденций B=||bij|| ориентированного графа G= без петель, где |V|=p, |U|=q, есть матрица размера p×q, элемент
- 9. Матрица циклов Z=||zij|| графа − матрица размерности m×n, m − количество циклов, n − число ребер,
- 10. Пример Неоднозначность представления графа матрицей циклов
- 11. По матрице смежностей можно однозначно восстановить граф: Матрица инциденций однозначно представляет граф: По матрице циклов нельзя
- 12. Выбор наилучшего представления определяется требованиями конкретной задачи Используются комбинации или модификации известных представлений Способы представления графов
- 13. Time-Out
- 14. Свойства модели: компактность представления информации о графе; привязка к распространенному математическому аппарату; наличие эффективных методов анализа
- 16. Скачать презентацию