Смешанный график

---

В теории графов смешанный граф G = ( V , E , A ) — это граф , состоящий из набора вершин V , набора (неориентированных) ребер E и набора направленных ребер (или дуг) A. ^[1]

Рассмотрим соседние вершины . Направленное ребро , называемое дугой , представляет собой ребро с ориентацией и может быть обозначено как или (обратите внимание, что это хвост и голова дуги). ^[2] Кроме того, ненаправленное ребро или ребро — это ребро без ориентации и может обозначаться как или . ^[2]${\ displaystyle u, v \ in V}$${\displaystyle {\overrightarrow {uv}}}$${\ displaystyle (u, v)}$${\displaystyle и}$${\displaystyle v}$${\displaystyle уф}$${\displaystyle [u,v]}$

В нашем примере приложения мы не будем рассматривать петли или кратные ребра смешанных графов.

Прогулка в смешанном графе — это последовательность вершин и ребер/дуг такая, что для всех индексов либо является ребром графа, либо является дугой графа. Этот обход является путем , если он не повторяет никаких ребер, дуг или вершин, за исключением, возможно, первой и последней вершин. Путь называется замкнутым, если его первая и последняя вершины совпадают, а замкнутый путь является циклом, если он не повторяет вершины, кроме первой и последней. Смешанный граф называется ациклическим, если он не содержит циклов.${\displaystyle v_{0},c_{1},v_{1},c_{2},v_{2},\dots ,c_{k},v_{k}}$${\displaystyle я}$${\displaystyle c_{i}=v_{i}v_{i+1}}$${\displaystyle c_{i}={\overrightarrow {v_{i}v_{i+1}}}}$

Раскраску смешанного графа можно рассматривать как маркировку или присвоение k различных цветов (где k — положительное целое число) вершинам смешанного графа. ^[3] Вершинам, соединенным ребром, необходимо назначить разные цвета. Цвета могут быть представлены числами от 1 до k , а для направленной дуги хвост дуги должен быть окрашен в меньшее число, чем начало дуги. ^[3]

---