Граф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер



Скачать 122.54 Kb.
Дата04.07.2013
Размер122.54 Kb.
ТипДокументы
Билет6

Граф – это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе – из рёбер. Вершины графа могут иметь произвольную природу, а вот каждое ребро – это всегда множество, состоящее из двух различных вершин; про ребро обычно говорят, что оно соединяет соответствующие вершины, а про вершины, что они являются концами соответствующего ребра. Две вершины графа называются смежными (соседними), если они соединены ребром. Вершина и ребро называются инцидентными, если вершина является одним из концов ребра. Степень вершины – это число ребер, инцидентных этой вершине. Граф называется полным, если любые его две вершины смежные. Степень графа – это наибольшая степень вершины в этом графе.

Сам термин «граф» происходит от латинского слова, означающего «рисунок». Использование терминов «граф», «вершина» и «ребро», происходит, по-видимому, исходя из графического представления графов в виде рисунков, где вершины представляются кружочками, а рёбра – линиями, соединяющими пары вершин.

Разумеется, графы можно представлять не только в виде рисунков. Другое популярное представление – в виде таблиц (или матриц) смежности. При таком представлении по графу строится квадратная таблица M, строчки и столбцы которой «именуются» вершинами графа (в произвольном, но в одинаковом и для строчек, и для столбцов порядке). На пересечении строки, соответствующей какой-либо вершине A, и столбца, соответствующего какой-либо вершине B, ставится значение M(A,B) равное 0 или 1 в зависимости от того, есть ли в графе ребро с концами в A и B или нет.

Легко видеть, что в матрице смежности M графа на т.н. «главной диагонали» (выделенной в приведенном примере жирным шрифтом) обязательно стоят нули: M(A,A) = 0 для всякой вершины графа A, т.к. дуга – это множество из двух вершин, а множество не может содержать повторяющихся элементов. Кроме того, матрица смежности обязательно симметрична относительно главной диагонали: M(A,B) = M(B,A) для любой пары вершин A и B.

Маршрут в графе – это или одна вершина, или произвольная конечная чередующаяся последовательность вершин и ребер, которая начинается и заканчивается на вершинах, в которой любое ребро в этой последовательности, соединяет предшествующую ему вершину с последующей ему вершиной:

вершина1

ребро1 (соединяющее вершину1 с вершиной2)

вершина2

ребро2 (соединяющее вершину2 с вершиной3)

…………………………………………………...

вершинаn

реброn (соединяющее вершинуn с вершиной(n+1)).

Число ребер n в таком маршруте называется его длиной. Соответственно, длину маршрута, состоящего из одной вершины, полагают равной нулю.

Говорят, что маршрут соединяет вершины png" name="рисунок 1" align=bottom width=20 height=14 border=0>и , они называются соответственно началом и концом маршрута, вершины называются промежуточными. Маршрут называется замкнутым, если .

Путь - это маршрут, в котором все ребра различны. Путь называется простым, если и все вершины в нем различны.

Цикл - это замкнутый путь. Цикл называется простым, если все вершины попарно различны.

Две вершины графа называются связанными, если существует маршрут, который начинается и заканчивается на этих вершинах. Соответственно, т.к. одиночная вершина – это маршрут, то считают, что всякая вершина связана сама с собой. Граф называется связным1, если его любые вершины связаны.

Граф называется двудольным, если его множество вершин распадается на два непересекающихся непустых множества (которые называются долями) так, что никакие две вершины из одной доли не соединены ребром. Полный двудольный граф – это двудольный граф, в котором любые две вершины из разных долей соединены ребром.

Взвешенный граф – это граф, в котором вершинам и/или ребрам сопоставлены некоторые неотрицательные вещественные числа, которые называются их весом. Различают графы, в которых вес приписан только вершинам (графами со взвешенными вершинами), графы, в которых вес приписан только ребрам (графами со взвешенными ребрами), и графы, в которых вес приписан и вершинам, и ребрам.

Ребра графа называются независимыми, если они не имеют общих вершин. Паросочетание – это произвольное множество независимых ребер графа. Паросочетание с максимально возможным числом ребер называется максимальным.

В интегрированную среду подготовки программ на Си или в компилятор языка как обязательный компонент входит препроцессор. Назначение препроцессора - обработка исходного текста программы до ее компиляции. Препроцессорная обработка включает несколько стадий, выполняемых последовательно. Конкретная реализация может объединять несколько стадий, но результат должен быть таким, как если бы они выполнялись в следующем порядке:

  1. Все системно-зависимые обозначения перекодируются в стандартные коды.

  2. Каждая пара из символов '\' и "конец строки" вместе с пробелами между ними убираются, и тем самым следующая строка исходного текста присоединяется к строке, в которой находилась эта пара символов.

  3. В тексте распознаются директивы и лексемы препроцессора, а каждый комментарий заменяется одним символом пустого промежутка.

  4. Выполняются директивы препроцессора и производятся макроподстановки.

  5. Эскейп-последовательности в символьных константах и символьных строках заменяются на их эквиваленты.

  6. Смежные символьные строки конкатинируются, то есть соединяются в одну строку.

  7. Каждая препроцессорная лексема преобразуется в текст на языке Си.

Поясним, что понимается под препроцессорными лексемами или лексемами препроцессора. К ним относятся символьные константы, имена включаемых файлов, идентификаторы, знаки операций, препроцессорные числа, знаки препинания, строковые константы и любые символы, отличные от пробела.

Стадия обработки директив препроцессора. При ее выполнении возможны следующие действия:

  • замена идентификаторов заранее подготовленными последовательностями символов;

  • включение в программу текстов из указанных файлов;

  • исключение из программы отдельных частей ее текста, условная компиляция;

  • макроподстановка, то есть замена обозначения параметризованным текстом, формируемым препроцессором с учетом конкретных аргументов.

Символические константы: #define

Если в качестве первого символа в строке программы используется символ #, то эта строка является командной строкой препроцессора (макропроцессора). Командная строка препроцессора заканчивается символом перевода на новую строку. Если непосредственно перед концом строки поставить символ обратной косой черты "\", то командная строка будет продолжена на следующую строку программы.

Директива #define, подобно всем директивам препроцессора, начинается c символа # в самой левой позиции. Она может появиться в любом месте исходного файла, а даваемое определение имеет силу от места появления до конца файла. Мы активно используем эту директиву для определения символических констант в наших примерах программ, однако она имеет более широкое применение, что мы покажем дальше.

Замена идентификаторов

#define идентификатор строка

Пример:

#define ABC 100

Заменяет каждое вхождение идентификатора ABC в тексте программы на 100:

#undef идентификатор

Пример:

#undef ABC

Отменяет предыдущее определение для идентификатора ABC.

Когда следует использовать символические константы? Вероятно, мы должны применять их для большинства чисел. Если число является константой, используемой в вычислениях, то символическое имя делает яснее ее смысл. Если число - размер массива, то символическое имя упрощает изменение вашей программы при работе с большим массивом. Если число является системным кодом, скажем для символа EOF, то символическое представление делает программу более переносимой. Изменяется только определение EOF. Мнемоническое значение, легкость изменения, переносимость: все это делает символические константы заслуживающими внимания!

!

Многие задачи можно решать, используя макроопределение с аргументами или функцию. Что из них следует применять? На этот счет нет строгих правил, но есть некоторые соображения.

Макроопределения должны использоваться скорее как хитрости, а не как обычные функции. Они могут иметь нежелательные побочные эффекты. Некоторые компиляторы ограничивают макроопределения одной строкой, и, по-видимому, лучше соблюдать такое ограничение, даже если ваш компилятор этого не делает.

Выбор макроопределения приводит к увеличению объема памяти, а выбор функции - к увеличению времени работы программы. Макроопределение создает строчный код, т.е. мы получаем оператор в программе. Если макроопределение применить 20 раз, то в программу вставится 20 строк кода. Если мы используем функцию 20 раз, то у нас будет только одна копия операторов функции. Однако управление программой следует передать туда, где находится функция, а затем вернуться в вызывающую программу, а на это потребуется больше времени, чем при работе со строчными кодами. Так что думайте, что выбирать!

Преимущество макроопределений заключается в том, что при их использовании нам не нужно беспокоиться о типах переменных, т.к. макроопределения имеют дело с символьными строками, а не с фактическими значениями. Tак наше макроопределение SQUARE(x) можно использовать одинаково хорошо с переменными типа int или float.

Запомним!

  1. В макроопределении нет пробелов, но они могут появиться в замещающей строке. Препроцессор полагает, что макроопределение заканчивается на первом пробеле, поэтому все, что стоит после пробела, остается в замещающей строке.

  2. Используйте круглые скобки для каждого аргумента и всего определения. Это является гарантией того, что элементы будут сгруппированы надлежащим образом в выражении.

  3. Для имен макрофункций следует использовать прописные буквы. Это соглашение не распространяется так широко, как соглашение об использовании прописных букв для макроконстант. Их применение предостережет от возможных побочных эффектов макроопределений.

Предположим, что мы разработали несколько макрофункций по своему усмотрению. Если мы пишем новую программу, мы не должны их переопределять. Нужно использовать директиву #include.

Включение файла: #include

Перечень обозначений заголовочных файлов для работы с библиотеками компиляторов утвержден стандартом языка. Ниже приведены названия этих файлов, а также краткие сведения о тех описаниях и определениях, которые в них включены. Большинство описаний - прототипы стандартных функций, а определены в основном константы, например EOF, необходимые для работы с библиотечными функциями.

assert.h - диагностика программ

ctype.h - преобразование и проверка символов

errno.h - проверка ошибок

float.h - работа с вещественными данными

limits.h - предельные значения целочисленных данных

locale.h - поддержка национальной среды

math.h - математические вычисления

setjump.h - возможности нелокальных переходов

signal.h - обработка исключительных ситуаций

stdarg.h - поддержка переменного числа параметров

stddef.h - дополнительные определения

stdio.h - средства ввода-вывода

stdlib.h - функции общего назначения (работа с памятью)

string.h - работа со строками символов

time.h - определение дат и времени

Командная строка #include может встречаться в любом месте программы, но обычно все включения размещаются в начале файла исходного текста.

#include <имя_файла>

Пример:

#include

Процессор заменяет эту строку содержимым файла math.h. Угловые скобки означают, что файл math.h будет взят из некоторого стандартного каталога (обычно это /usr/include). Текущий каталог не просматривается:

#include "имя_файла"

Пример:

#include "ABC"

Препроцессор заменяет эту строку содержимым файла ABC. Так как имя файла заключено в кавычки, то поиск производится в текущем каталоге (в котором содержится основной файл исходного текста). Если в текущем каталоге данного файла нет, то поиск производится в каталогах, определенных именем пути в опции -l препроцессора. Если и там нет файла, то просматривается стандартный каталог

По соглашению суффикс .h используется для заголовочных файлов, т.е. файлов с информацией, которая располагается в начале программы. Заголовочные файлы обычно состоят из операторов препроцессора.

Некоторые файлы включены в систему, например, stdio.h, но можно создать и свой файл.

Многие программисты разрабатывают свои стандартные заголовочные файлы, чтобы использовать их в программах.

Условная компиляция


Командные строки препроцессора используются для условной компиляции различных частей исходного текста в зависимости от внешних условий.

#if константное_выражение

Пример:

#if ABC + 3

Истина, если константное выражение ABC + 3 не равно нулю.

#ifdef идентификатор

Пример:

#ifdef ABC

истина, если идентификатор ABC определен ранее командой #define.

#ifndef идентификатор

Пример:

#ifndef ABC

истина, если идентификатор ABC не определен в настоящий момент.

#else

. . .

#endif

Если предшествующие проверки #if, #ifdef или #ifndef дают значение "Истина", то строки от #else до #endif игнорируются при компиляции.

Если эти проверки дают значение "Ложь", то строчки от проверки до #else (а при отсутствии #else - до #endif) игнорируются.

Команда #endif обозначает конец условной компиляции.

Пример:

#ifdef DEBUG

fprintf (stderr, "location: x = %d\n", x);

#endif

Вспомогательные директивы

Номер строки и имя файла


#line целая_константа "имя_файла"

Пример:

#line 20 "ABC"

Препроцессор изменяет номер текущей строки и имя компилируемого файла. Имя файла может быть опущено.

Одна из целей использования условной компиляции - сделать программу более мобильной. Изменяя несколько ключевых определений в начале файла, мы можем устанавливать различные значения и включать различные файлы для разных систем.

Пример:

#define N 3/*определение константы */

void main( )

{

#line 55 "file.c"

double x[3*N];

}

Реакция на ошибки


#error последовательность лексем

Обработка директивы приводит к выдаче диагностического сообщения в виде, определенном последовательностью лексем. Применение этой директивы совместно с условными препроцессорными командами.

Пример:

#define NAME 15

В дальнейшем можно проверить ее значение и выдать сообщение, если у NAME окажется другое значение:

#if (NAME !=15)

#error NAME должно быть равно 15!

Сообщение будет выглядеть так:

error <имя_файла><номер_строки >;

error directive: NAME должно быть равно 15!

Пустая директива


#

Использование этой директивы не вызывает никаких действий.

Встроенные макроимена


Существуют встроенные (заранее определенные) макроимена, доступные препроцессору во время обработки. Они позволяют получить следующую информацию:

_DATA_ - строка символов в формате: "месяц число год", определяющая дату начала обработки исходного файла. Например, после препроцессорной обработки текста программы, выполненной 29 января 2005 года, оператор

printf(_DATA_);

станет таким

printf("%s", "January 29 2005");

_LINE_ - десятичная константа - номер текущей обрабатываемой строки файла с программой на Си. Принято, что номер первой строки исходного файла равен 1;

_FILE_ - строка символов - имя компилируемого файла. Имя изменяется всякий раз, когда препроцессор встречает директиву #include с указанием имени другого файла. Когда включения файла по команде #include завершаются, востанавливается предыдущее значение макроимени _FILE_;

_TIME_ - строка символов вида "часы:минуты:секунды", определяющая время начала обработки препроцессором исходного файла;

_STDC_ - константа, равная 1, если компилятор работает в соответствии с ANSI-стандартом. В противном случае значение микроимени _STDC_ не определено. Стандарт языка Си предполагает, что наличие имени _STDC_ определяется реализацией, так как макрос _STDC_ относится к нововведениям стандарта. В конкретных реализациях набор предопределенных имен гораздо шире. Для получения более полных сведений о предопределенных препроцессорных именах следует обращаться к документации по конкретному компилятору.

1 Обратите внимание «связным», а не «связанным».

Похожие:

Граф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер iconИзобразить неориентированный граф, содержащий не менее семи вершин. Построить для него матрицы смежности и инцидентности
Графом g называется совокупность двух множеств: вершин V и рёбер E, между элементами которых определено отношение инцидентности (т...
Граф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер icon1. Основные понятия и определения
Пишут G=(V, E). Если пара вершин неупорядочена, то ее принято называть ребром, если упорядочена – дугой. Граф, состоящий только из...
Граф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер iconОсновные понятия теории графов
Т. е граф – это пара G=(V,E), где V множество вершин, а e семейство пар ребер ei=(vi1, vi2), vij принадлежит V. Вершины графа можно...
Граф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер iconДать определения понятиям
Построить модель сети в виде графа. Задать нумерацию вершин с Задать граф в виде матрицы смежности. Задать граф в виде списка ребер...
Граф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер iconРебром, упорядоченная пара – дугой. Граф, содержащий только ребра, называется неориентированным
Граф, содержащий только дуги, – ориентированным. Пара вершин может соединяться двумя или более ребрами (дугами одного направления),...
Граф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер iconЛекция 4 Теория графов
Граф – совокупность множества вершин V и множества пар вида (V,w)X, V,wV. Множество вершин всегда непусто. X – множество ребер
Граф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер iconЭволюция в графах
Как правило, граф представляют как статичный объект, свойства которого выражаются константным набором вершин и ребер. В зависимости...
Граф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер iconЗадача Нарисуйте граф с множеством вершин и множеством рёбер Выпишите его матрицу смежности

Граф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер iconГрафы, в которых окрестности вершин – псевдогеометрические графы для
Г на множестве всех вершин, находящихся на расстоянии i от a. Положим. Если граф зафиксирован, то вместо будем писать. Для множества...
Граф это пара конечных множеств, первое из которых состоит из вершин (или узлов), а второе из рёбер iconМонография «Манипуляции массами и психоанализ»
Классический и постклассический психоанализ (или глубинная психология), как известно, состоит из двух направлений практического применения....
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org