Основы теории графов
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ Графом называется тройка , где M — непустое конечное множество вершин, N — конечное множество дуг, соединяющих вершины, T — отображение из N в M × M, которое сопоставляет каждой дуге упорядоченную пару вершин. Первая из них называется началом этой дуги, а вторая — концом дуги. M ={A, B, C, D, E} N = {1, 2, 3, 4, 5}, T(1) = (D,A); T(2) = (D,B); T(3) = (B,C); T(4) = (C,E); T(5) = (E,D); Ребро – неориентированная дуга. Граф называется неориентированным, если каждая его дуга не ориентирована, ориентированным (орграфом), если ориентированы все его дуги, смешанным, если есть как ориентированные, так и неориентированные дуги. Петля – это дуга, начальная и конечная вершина которой совпадают. Вершины, прилегающие к одному и тому же ребру, называются смежными. Полным называется граф, в котором каждые две вершины смежные.
ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ
Slaidy.com
