Mixed graph | EPFL Graph Search

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 GraphSearch.

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 .

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.

Related concepts (3)

Related courses (4)

Related lectures (52)

Mixed graph

Graph (discrete mathematics)

In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called vertices (also called nodes or points) and each of the related pairs of vertices is called an edge (also called link or line). Typically, a graph is depicted in diagrammatic form as a set of dots or circles for the vertices, joined by lines or curves for the edges.

Graph theory

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices (also called nodes or points) which are connected by edges (also called links or lines). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics.

ME-427: Networked control systems

This course offers an introduction to control systems using communication networks for interfacing sensors, actuators, controllers, and processes. Challenges due to network non-idealities and opportun

CS-250: Algorithms I

The students learn the theory and practice of basic concepts and techniques in algorithms. The course covers mathematical induction, techniques for analyzing algorithms, elementary data structures, ma

COM-406: Foundations of Data Science

We discuss a set of topics that are important for the understanding of modern data science but that are typically not taught in an introductory ML course. In particular we discuss fundamental ideas an

Exponential Family COM-406: Foundations of Data Science

Covers the concept of the exponential family and discusses forward and backward maps, expensive computations, parameters, functions, and convexity.

Networked Control Systems: Laplacian Matrix and Consensus in Continuous Time ME-427: Networked control systems

Explores the Laplacian matrix properties and consensus in continuous time.

Arrays and Vectors in C++CS-119(c): Information, Computation, Communication

Covers the basics of arrays and vectors in C++, including direct access to elements and specific methods, and concludes with a demo of the 'Propagatio' project.