infa_1 / 27.Теория графов и ее использование в программировании

27.Теория графов и ее использование в программировании.

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

Граф (сеть).

G=(V,E) состоит из конечного множества m-вершин (m≥1) и конечного множества n-неупорядоченных пар элементов (n≥0).

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

2 вершины V и U называются смежными, если в графе G существует ребро (u,v). В противном случае V и U – независимые. Про ребро (u,v) так же говорят, что оно инцидентно вершинам V и U.

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

Граф называется полным, если каждая вершина связана с другой.