Can we have undirected edges and directed edges in a graph

Question

Suppose there are 3 vertices in a graph. They are connected as a to b, b to a, b to c and a to c.

Then, we can draw just a line without arrows between a and b as it has arrows in both directions and keep the other edges with arrows?

Can we have a graph with directed edges and undirected edges like that?

Answer 1

In most cases, we do not mix the two types of edges.

When describing some kind of relationship, we usually pick an undirected graph as a model when the relationship is inherently symmetric: for example, if you wanted to look at the Facebook friendships between a group of people. If the relationship is not inherently symmetric - if there's the possibility that it could be asymmetric - then we look at a directed graph as a model. For example, if you wanted to look at Twitter follows between the same group of people, you would use a directed graph.

We would keep that separation if, miraculously, this group of people happened to only follow each other on Twitter mutually - if the relationship happened to be symmetric. This would be represented by a directed graph where every pair of adjacent vertices had edges both ways. All the more so, if some Twitter follows were mutual, we would still represent them by a pair of directed edges in both directions.

Mixed graphs do exist, but they exist for other purposes.

We use mixed graphs in situations where an undirected edge represents a symmetric relationship beyond what a pair of directed edges in both directions could express. Take a look at the two applications given in Wikipedia's article on mixed graphs:

Mixed graphs may be used to model job shop scheduling problems in which a collection of tasks is to be performed, subject to certain timing constraints. In this sort of problem, undirected edges may be used to model a constraint that two tasks are incompatible (they cannot be performed simultaneously). Directed edges may be used to model precedence constraints, in which one task must be performed before another. A graph defined in this way from a scheduling problem is called a disjunctive graph. The mixed graph coloring problem can be used to find a schedule of minimum length for performing all the tasks.

Undirected edges in this application are not the same as a pair of directed edges. If you have directed edges $x \to y$ and $y \to x$, that would represent two tasks where $x$ has to be done before $y$, but $y$ has to be done before $x$. Outside of dystopian bureaucracy, that should not happen in job scheduling problems. An undirected edge $xy$ represents the weaker constraint that $x$ and $y$ should not in progress at the same time.

Mixed graphs are also used as graphical models for Bayesian inference. In this context, an acyclic mixed graph (one with no cycles of directed edges) is also called a chain graph. The directed edges of these graphs are used to indicate a causal connection between two events, in which the outcome of the first event influences the probability of the second event. Undirected edges, instead, indicate a non-causal correlation between two events. A connected component of the undirected subgraph of a chain graph is called a chain. A chain graph may be transformed into an undirected graph by constructing its moral graph, an undirected graph formed from the chain graph by adding undirected edges between pairs of vertices that have outgoing edges to the same chain, and then forgetting the orientations of the directed edges.

Here, once again, the undirected edges mean something qualitatively different from a pair of directed edges. From the beginning, in fact, a chain graph is required to have no cycles made up of directed edges: this means, in particular, that we cannot have a pair of directed edges going both ways between the same two vertices.