31. Краткое введение (о чем идет речь )

1.1. Основы теории графов (это очевидно, но это необходимо кратко

1.2. Генетические алгоритмы как метод оптимизации

1.3. Что мы будем делать в работе

1.4. Приложение идеи на практике ( где можно использовать )

2. Конкретная постановка задачи ( тривиально выражаясь: из пункта А в пункт Б поступает поток и т.д. и т.п. )

3. Примерное направление решения

1.1. Основы теории графов (это очевидно, но это необходимо кратко перечислить). Здесь потом оставить или добавить те термины и определения, которые реально будут использоваться в работе.

Графы представляют собой наиболее абстрактную структуру, с которой приходится сталкиваться в теории ЭВМ (computer science). Графы используются для описания алгоритмов автоматического проектирования, в диаграммах машины конечных состояний, при решении задач маршрутизации потоков и т.д. Любая система, предполагающая наличие дискретных состояний или наличие узлов и переходов между ними, может быть описана графом. Соединения между узлами графа называются ребрами. Если узлы графа не нумерованы, то ребра являются неориентированными. У графа с нумерованными узлами ребра ориентированы. Ребрам могут быть присвоены определенные веса или метки.

Граф представляет собой структуру П = , в которой V представляет собой конечный набор узлов. Ребра не могут иметь общих точек кроме вершин (узлов) графа. Замкнутая кривая в E может иметь только одну точку из множества V, а каждая незамкнутая кривая в E имеет ровно две точки множества V. Если V и E конечные множества, то и граф им соответствующий называется конечным. Граф называется вырожденным, если он не имеет ребер. Параллельными ребрами графа называются такие, которые имеют общие узлы начала и конца.

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

Граф G называется плоским, если его можно отобразить в плоскости без пересечения его граней.

Очертанием графа (face) считается любая топологически связанная область, ограниченная ребрами графа.

Неориентированный граф G = называется связанным, если для любых двух узлов x,y из V существует последовательность ребер из набора E, соединяющая x и y.

Граф G связан тогда и только тогда, когда множество его вершин нельзя разбить на два непустых подмножества V1 и V2 так, чтобы обе граничные точки каждого ребра находились в одном и том же подмножестве.

Граф G называется k-связным, если не существует набора из k-1 или меньшего числа узлов, такого, что удаление всех узлов V' и сопряженных с ними ребер, сделают

нет

Примечаний нет.