Мы надеемся, что в этом разделе нам удалось показать, что теория графов также может быть сформулирована в терминах теории множеств и что графы играют важную роль даже при построении графиков.
Алгоритм — пошаговая последовательность действий по решению задачи.
Вершина — точка графа, где сходится одно или более ребер; также может быть изолированной.
Вес — значение, поставленное в соответствие ребру графа, означающее стоимость, расстояние, время и пр.
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некоторое число.
Гамильтонов граф — граф, в котором существует гамильтонов цикл.
Гамильтонов цикл — цикл, содержащий все вершины графа ровно по одному разу.
Гомеоморфные графы — графы, один из которых получается из другого путем добавления или удаления вершин степени 2. Если в таких графах удалить все вершины степени 2, полученные графы будут одинаковыми.
Грань — область, ограниченная ребрами плоского графа.
Граф — совокупность множества точек (вершин) и линий (ребер), соединяющих некоторые точки.
Дерево — связный граф, не содержащий циклов.
Дуга — ориентированное ребро графа. Изображается стрелкой.
Изоморфные графы — графы, между вершинами и ребрами которых существует взаимно однозначное соответствие, которое сохраняет смежность и инцидентность.
Критический путь — путь максимальной длины в ориентированном графе.
Лес — множество графов, которые являются деревьями.
Матрица инцидентности графа — матрица
Метка — информация, присвоенная вершинам и ребрам графа; например, числа, слова, наименования.
Оптимальное решение — наилучшее решение (согласно некоему количественному показателю) из множества возможных решений.
Органиграмма — граф, упорядочивающий информацию, устройство организации или действия, которые необходимо выполнить для решения задачи.
Орграф (ориентированный граф) — граф, все ребра которого являются ориентированными, то есть дугами.
Остовное дерево графа — подграф данного графа с максимально возможным числом ребер, который является деревом.
Петля — дуга или ребро, начало и конец которого находятся в одной и той же вершине.
Плоский граф — граф, ребра которого не имеют никаких общих точек, кроме вершин, в которых они сходятся.
Подграф — граф, содержащий некое подмножество вершин и ребер данного графа.
Полный граф — граф, в котором любая пара вершин соединена ребром.
Поток — некая величина, сопоставленная ребру, дуге или графу.
Путь — последовательность смежных ребер или дуг.
Раскраска графа — присвоение цветов вершинам, ребрам или граням графа при выполнении определенных условий.
Ребро — связь между двумя вершинами графа.
Связный граф — граф, в котором для любых двух вершин существует соединяющий их простой путь.
Сеть — граф, используемый для решения транспортных задач и задач распределения.
Смежные дуги — две дуги, имеющие общую вершину.
Смежные ребра — два ребра, имеющие общую вершину.
Степень вершины — количество ребер графа, сходящихся в данной вершине.
Траектория — то же, что и путь.
Узел — то же, что и вершина.
Цикл — путь, начало и конец которого находятся в одной и той же вершине.
Эйлеров граф — граф, в котором существует эйлеров цикл.
Эйлеров цикл — цикл, проходящий через каждое ребро графа ровно один раз.
—: Tres aspectos de matemática у diseño, Barcelona, Tusquets, 1969.
—: у
—: Graphs and Hypergraphs, Amsterdam, North-Holland, 1973.
![Золотое сечение [Математический язык красоты] (Мир математики. т.1.)](/_next/image?url=https%3A%2F%2Fimg.chitka.online%2Feboox-media%2Fcovers%2Fe0c8168082bc52f2c7dbc629a35444c2.jpg&w=828&q=75)
