10.1 Graphs and Graph Models Flashcards
Graph:
Visualize it?
A graph G = (V, E) consists of V, a nonempty set of vertices (or nodes) and E, a set of edges.
Points represent vertices and lines (curved as well ) represent edge.
What is an edge:
Each edge has either one or two vertices associated with it, called its endpoints. An edge is
said to connect its endpoints.
FInite and Infinite Graphs?
The set of vertices V of a graph G may be infinite. A graph with an infinite vertex
set or an infinite number of edges is called an infinite graph, and in comparison, a graph with
a finite vertex set and a finite edge set is called a finite graph
Crossing edges:
When we draw a graph, we generally try to draw edges so that they do
not cross. However, this is not necessary because any depiction using points to represent vertices
and any form of connection between vertices can be used.
The key point is that
the way we draw a graph is arbitrary, as long as the correct connections between vertices are
depicted.
Simple Graph:
A graph in which each edge connects two different vertices and where
no two edges connect the same pair of vertices is called a simple graph.
Note that in a simple
graph, each edge is associated to an unordered pair of vertices, and no other edge is associated
to this same edge. Consequently, when there is an edge of a simple graph associated to {u, v},
we can also say, without possible confusion, that {u, v} is an edge of the graph.
Multigraphs :
Graphs that may have multiple edges connecting the same vertices are called
multigraphs. When there are m different edges associated to the same unordered pair of vertices
{u, v}, we also say that {u, v} is an edge of multiplicity m. That is, we can think of this set of
edges as m different copies of an edge {u, v}.
Pseudographs :
Graphs that may include loops, and possibly
multiple edges connecting the same pair of vertices or a vertex to itself, are sometimes called
pseudographs
Digraph :
A directed graph (or digraph) (V, E) consists of a nonempty set of vertices V and a set of directed edges (or arcs) E. Each directed edge is associated with an ordered pair of vertices. The directed edge associated with the ordered pair (u, v) is said to start at u and end at v.
Note that we obtain a directed graph when we assign a direction to each edge in an undirected
graph.
Simple directed graph
When a directed graph has no loops and has no multiple directed edges, it is called a
simple directed graph. Because a simple directed graph has at most one edge associated to each
ordered pair of vertices (u, v), we call (u, v) an edge if there is an edge associated to it in the graph.
Directed multigraphs :
Directed graphs that may have multiple directed edges
from a vertex to a second (possibly the same) vertex.
When there are m directed edges, each associated to
an ordered pair of vertices (u, v), we say that (u, v) is an edge of multiplicity m.
Mixed graph :
For some models we may need a graph where some edges are undirected, while others are
directed. A graph with both directed and undirected edges is called a mixed graph.
Graph terminology, Use of term graph in this book:
use the table 1 to revise.
Type Edges Multiple Edges Allowed Loops allowed
6
or what questions can help to understand the structure of graph.
We will sometimes use the term graph as a general term to describe graphs with directed or undirected edges
(or both), with or without loops, and with or without multiple edges. At other times, when the
context is clear, we will use the term graph to refer only to undirected graphs.
▶ Are the edges of the graph undirected or directed (or both)?
▶ If the graph is undirected, are multiple edges present that connect the same pair of vertices? If the graph is directed, are multiple directed edges present?
▶ Are loops present?
Intersection graph:
The intersection graph of a collection of sets A1,
A2,… , An is the graph that has a vertex for each of these
sets and has an edge connecting the vertices representing two sets if these sets have a nonempty intersection.
