Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Mixed graph
Summary
In graph theory, a mixed graph G = (V, E, A) is a graph consisting of a set of vertices V, a set of (undirected) edges E, and a set of directed edges (or arcs) A.
Consider adjacent vertices . A directed edge, called an arc, is an edge with an orientation and can be denoted as or (note that is the tail and is the head of the arc). Also, an undirected edge, or edge, is an edge with no orientation and can be denoted as or .
For the purpose of our application example we will not be considering loops or multiple edges of mixed graphs.
A walk in a mixed graph is a sequence of vertices and edges/arcs such that for all indices , either is an edge of the graph or is an arc of the graph. This walk is a path if it does not repeat any edges, arcs, or vertices, except possibly the first and last vertices. A path is closed if its first and last vertices are the same, and a closed path is a cycle if it does not repeat vertices, except the first and the last. A mixed graph is acyclic if it does not contain a cycle.
Mixed graph coloring can be thought of as a labeling or an assignment of k different colors (where k is a positive integer) to the vertices of a mixed graph. Different colors must be assigned to vertices that are connected by an edge. The colors may be represented by the numbers from 1 to k, and for a directed arc, the tail of the arc must be colored by a smaller number than the head of the arc.
For example, consider the figure to the right. Our available k-colors to color our mixed graph are {1, 2, 3}. Since u and v are connected by an edge, they must receive different colors or labelings (u and v are labelled 1 and 2, respectively). We also have an arc from v to w. Since orientation assigns an ordering, we must label the tail (v) with a smaller color (or integer from our set) than the head (w) of our arc.
A (strong) proper k-coloring of a mixed graph is a function c : V → [k] where [k] := {1, 2, ..., k} such that c(u) ≠ c(v) if uv ∈ E and c(u) < c(v) if .
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.