Теория графов

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

Дерево -- граф, без циклов.
Полный граф<.b> -- проведены все возможные ребра.

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

Простой цикл -- вершины присутствующие в его определении никогда не повторяются.

Цепь -- незамкнутый маршрут.
Простая цепь -- все вершины не повторяются.

Ациклический граф -- граф без циклов.

Связность графа. Граф связный (не связанный) -- для любых двух вершин этого графа существует маршрут соединяющий эти две вершины.

Дерево -- связный ациклический граф.

Эквивалентный определения дерева.

Дерево:
1. Связный граф у которого любые две вершины соединены единственной простой цепью.
2. Связный граф у которого число ребер на единицу меньше числа вершин.
3. Ациклический граф у которого число ребер на единицу меньше числа вершин.

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

Эйлеровский цикл -- проходит по каждому ребру графа один раз. (мосты Кенига)

Для связанного графа следующие три утверждения эквивалентны:

1. В графе есть эйлеровский цикл (эйлеровский граф).
2. Множество ребер графа распадаются в объединении непересекающихся (по ребрам) простых циклов.
3. Степень каждой вершины четна.

Степень вершины -- количество ребер сопряженных с ней. (для мультиграфа). Или число ребер инцидентных данныой вершине.
Локальная степень вершины -- число только входящих, или только исходящих ребер данной вершины.

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

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

Для каждого ориентированного графа существует также соотнесенный неориентированный граф, ребрами которого являются ребра текущего графа, но уже без ориентаций.

Граф называеся однородным (regular) степени n, если локальные степени во всех его вершинах равны n.

Add new comment

Filtered HTML

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <blockquote> <code> <ul> <ol> <li> <dl> <dt> <dd>
  • Lines and paragraphs break automatically.

Plain text

  • Web page addresses and e-mail addresses turn into links automatically.
  • Lines and paragraphs break automatically.
CAPTCHA
This question is for testing whether or not you are a human visitor and to prevent automated spam submissions.
2 + 0 =
Solve this simple math problem and enter the result. E.g. for 1+3, enter 4.