ПОИСК Статьи Чертежи Таблицы Некоторые сведения из теории графов из "Графы зубчатых механизмов " Прежде чем перейти непосредственно к графам, договоримся сначала о ряде обозначений и определений, касающихся теории множеств. [c.9] Например, множество натуральных чисел от 1 до п можно записать так (1, 2,. .., /j = 1 п. [c.9] используя обозначение 1 п, множество Z будем чаще записывать в виде Z = a[ n, где а,-= = a[i]—элемент множества Z. Запись b Z обозначает, что Ъ не является элементом множества Z. Символ 0 обозначает пустое множество. [c.9] Множество Л, состоящее из элементов множества Z, называется подмножеством множества Z. В этом случае записывают A Z или 7эЛ. Если при этом хотя бы один элемент из Z не входит в Л, то помимо знака S можно использовать знак строгого включения AdZ. В частности, если Adl z, то а[Л]с1 za[l z]= аи 2.а . [c.10] Как обычно, А[]В — множество, называемое объединением Л и В и состоящее из элементов Л и В А[ В — множество, называемое пересечением Л и fi и включающее элементы, принадлежащие как Л, так и В Л В — множество, называемое разно-стьюЛ и В и состоящее из элементов множества Л, не принадлежащих В. Если В — одноэлементное множество, т. е. S = Ь , то Л будем записывать и проще А — Ь. Число элементов в множестве Л будем обозначать таким образом Л =га. [c.10] При изложении материала по теории графов в основном будем придерживаться работ [31] и [8]. [c.11] Вершины а, р, входящие в некоторое ребро (а, р) графа, называются смежными. [c.11] Существует много способов задания (представлений) графов. В этой книге в основном будут использованы только три. [c.11] Первый из них предполагает полное описание множества ребер в виде списка ребер. Пусть Z = = а[1 8], тогда список ребер ( i, j), (а,, Оз), (а,, аД ( 2, аз), (аз, ai), ( 4, 5). ( 5, б), ( 5- з), ( 6. aj), (а , а ), (fl7, flg) однозначно определяет некоторый граф Psi содержащий восемь вершин и одиннадцать ребер. [c.11] Заметим, что в списке ребер (оь а/) = (а,-, а,), т. е. пара считается неупорядоченной. [c.12] Второй способ связан с геометрическим представлением графа. На плоскость наносятся jZ — 2 точек. Далее точки а и 6 соединяются произвольным образом непрерывной линией, если ребро (а, Ь) и. Так, на рис. 1.3 приведено три различных представления на плоскости одного и того же графа Га. [c.12] Такая матрица называется матрицей смежностей графа. [c.12] Очевидно, она полностью задает его и от нее легко перейти к любому другому представлению графа и обратно. [c.12] Вторая матрица, полностью характеризующая граф, называется матрицей инциденций. [c.12] Так как любое ребро инцидентно только двум вершинам, то любая строка матрицы инциденции содержит ровно две единицы. [c.13] Число вершин, смежных с данной вершиной /, / е Z, называется степенью этой вершины s/. Очевидно, она равна числу инцидентных к ней ребер. В связи с этим число единиц в j-й строке, в j-м столбце матрицы смежностей и в /-м столбце матрицы инциденций равно s,-. [c.13] Всякое представление графа связано с тем или иным обозначением (нумерацией) вершин и ребер. Любое переобозначение элементов графа приводит к разным его представлениям (например, матрицы смежностей или инцидентностей могут отличаться друг от друга перестановкой строк и столбцов). [c.13] Взаимнооднозначное отображение f Z Z множества Z снова в Z, сохраняющее смежность вершин, называется автоморфизмом графа Г. Другими словами, автоморфизм есть изоморфизм графа в себя. [c.14] В дальнейшем под графом будем понимать то или иное его представление, при этом чаще всего будем пользоваться геометрическим представлением как более наглядным и удобным для изучения графовых объектов. [c.14] у которой начальная i и конечная ап вершины совпадают, называется циклом. Его длина совпадает с длиной образующей цепи. Цикл, содержащий все вершины графа, называется гамильтоновым. [c.14] Вернуться к основной статье