Терминология - теория - граф
Cтраница 1
Терминология теории графов все еще не стандартизирована. Некоторые авторы предпочитают терминам вершина и ребро термины точка и линия. Однако употребление таких терминов может создать неудобства в задачах, в которые входят одновременно графы и геометрические или топологические структуры. [1]
Используя терминологию теории графов, приведенную в разд. I можно назвать цветными: в каждой стадии есть, по крайней мере, одна реакция - дуга, окрашенная в цвет наблюдаемого вещества, участвующего в реакции. [2]
В настоящем разделе дается формальное определение графа и вводится основополагающая терминология теории графов. Приводятся примеры графов и некоторые простые теоремы. [3]
Увы, необходимо сформулировать ряд определений, чтобы в дальнейшем иметь возможность использовать основные понятия и терминологию теории графов. После этого мы дадим краткое введение в учение о полных подграфах, в теорию экстремальных графов ( которая изучает графы с запрещенными подграфами), в исследование свойств графов пересечений ( в которых вершинами являются множества, а непустые пересечения представляют смежность); будут определены также полезные операции на графах. [4]
 |
Результаты алгоритма ближайший сосед. [5] |
Применение процедуры можно рассматривать как получение графа, в котором ребра соединяют все вершины в группу. Пользуясь терминологией теории графов, можно сказать, что каждая группа образует полный подграф. Расстояние между двумя группами определяется наиболее удаленными вершинами в этих двух группах. [6]
Процесс решения задачи применительно к определению оптимального порядка запуска предметов на линию основан на переходе от множества всех последовательностей обработки различных предметов к более мелким подмножествам и вычислении для каждого из них нижней границы затрат времени на переналадки. Все множество последовательностей запуска различных предметов на линию представляется в терминологии теории графов вершиной дерева, подмножества - как узлы дерева, а процесс разделения подмножеств - как разветвление дерева. [7]
В этой главе мы приступаем к важнейшей проблематике книги - к теории оптимальных потоков в сетях. Для того чтобы определить сами сети и потоки, воспользуемся широко распространившейся сейчас терминологией теории графов, которая в основном будет введена ( с необходимыми фактами теоретического и вычислительного характера) в первых трех параграфах. [8]
Когда для измерения расстояния между подмножествами используется dmm, ближайшие соседи определяют ближайшие подмножества. Поскольку ребра, соединяющие группы, всегда проходят между различными группами, результирующий граф никогда не имеет замкнутых контуров или цепей; пользуясь терминологией теории графов, можно сказать, что эта процедура генерирует дерево. Если так продолжать, пока все подмножества не будут соединены, в результате получим покрываю-шее дерево ( остов) - дерево с путем от любой вершины к любой другой вершине. [9]
Харари активно участвует во многих конференциях по теории графов и смежным с ней наукам и неизменно является редактором трудов таких конференций. Одна из целей ( и притом весьма нелегкая), которая, как можно судить по характеру книги, поставлена Харари, состоит в попытке унифицировать обозначения и упорядочить терминологию теории графов. Однако, как признает сам автор, эта попытка, возможно, не будет очень удачной из-за большого разнобоя в терминологии и обозначениях в современной литературе в этой области. Следует отметить, что книга очень популярна среди зарубежных ( особенно американских) специалистов, связанных по своей работе с дискретной математикой, и большинство ссылок в статьях и кратких сообщениях по теории графов приходится на долю этой книги. [10]
Главы 2 - - 4 посвящены тоновым изображениям и основное внимание в них уделяется преобразованиям и статистическим методам. Необходимым условием понимания всех четырех глав, в которых речь идет только об изображениях класса 1, является вводный курс по обработке сигналов. Остальной материал книги не требует такой подготовки. Все алгоритмы, представленные в этих трех главах, являются фактически алгоритмами обхода графа. Предполагается знакомство читателя с терминологией теории графов. Главы 10 - 13 посвящены построению кривых и поверхностей по точкам. Хотя формально изложенный в них материал базируется на простейших сведениях из анализа, все же некоторая математическая культура здесь не помешает. Главы 14 - 17 посвящены методам формирования графических отображений и их математическому фундаменту - линейной алгебре. [11]
Большинство специалистов по теории графов употребляют в книгах, статьях и лекциях свою собственную терминологию. На конференциях по теории графов каждый выступающий, чтобы избежать неправильного понимания, считает необходимым определить прежде всего язык, которым он будет пользоваться. Даже само слово граф не является священным. Некоторые авторы действительно определяют граф как граф 2), другие же имеют в виду такие понятия, как мультиграф, псевдограф, ориентированный граф или сеть. Нам кажется, что единообразие в терминологии теории графов никогда не будет достигнуто, но, может быть, оно и не к чему. [12]
Страницы: 1