графы в информатике являются способом определения отношений в совокупности элементов. это основные объекты изучения теории графов.
базовые определения
из чего состоит граф в информатике? он включает множество объектов, называемых вершинами или узлами, некоторые пары которых связаны т. н. ребрами. например, граф на рисунке (а) состоит из четырех узлов, обозначенных а, в, с, и d, из которых b соединен с каждой из трех других вершин ребрами, а c и d также соединены. два узла являются соседними, если они соединены ребром. на рисунке показан типичный способ того, как строить графы по информатике. круги представляют вершины, а линии, соединяющие каждую их пару, являются ребрами.
какой граф называется неориентированным в информатике? у него отношения между двумя концами ребра являются симметричными. ребро просто соединяет их друг с другом. во многих случаях, однако, необходимо выразить асимметричные отношения – например, то, что a указывает на b, но не наоборот. этой цели служит определение графа в информатике, по-прежнему состоящего из набора узлов вместе с набором ориентированных ребер. каждое ориентированное ребро представляет собой связь между вершинами, направление которой имеет значение. направленные графы изображают так, как показано на рисунке (b), ребра их представлены стрелками. когда требуется подчеркнуть, что граф ненаправленный, его называют неориентированным.
Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг. В своей книге "Об индийском счете" он изложил правила записи натуральных чисел с арабских цифр и правила действий над ними "столбиком", знакомые теперь каждому школьнику. В XII веке эта книга была переведена на латынь и получила широкое рас в Европе.
Человек ежедневно встречается с необходимостью следовать тем или иным правилам, выполнять различные инструкции и указания. Например, переходя через дорогу на перекрестке без светофора надо сначала посмотреть направо. Если машин нет, то перейти полдороги, а если машины есть, ждать, пока они пройдут, затем перейти полдороги. После этого посмотреть налево и, если машин нет, то перейти дорогу до конца, а если машины есть, ждать, пока они пройдут, а затем перейти дорогу до конца.
В математике для решения типовых задач мы используем определенные правила, описывающие последовательности действий. Например, правила сложения дробных чисел, решения квадратных уравнений и т. д. Обычно любые инструкции и правила представляют собой последовательность действий, которые необходимо выполнить в определенном порядке. Для решения задачи надо знать, что дано, что следует получить и какие действия и в каком порядке следует для этого выполнить. Предписание, определяющее порядок выполнения действий над данными с целью получения искомых результатов, и есть алгоритм.