Week 9 Flashcards
What are graphs?
Graphs are data structures where each node may have many predecessors and many successors.
Graphs are generalizations of tree structures, which are a generalization of linear structures.
What does a graph G=(V,E) consist of?
A graph consists of
* A non empty set of vertices(nodes)
* A (possibly) empty set of edges (arcs) that connect vertices.
What is an undirected graph?
Unordered pairs of graphs are unordered pairs of vertices.
* Edges represent an unordered relation between vertices
* Edges are represented undirected arcs
* Edges are always bidirectional.
What is a directed graph?
Ordered pairs of vertices
* edges represent direction between vertices
* Edges are represented by arrows.
* Edges are unidirectional, but can be bidirectional.
What does it mean for two vertices to be adjacent?
Two vertices are adjacent if an edge directly connects them.
If directed the first endpoint is the orgin, and the other is the destination.
What is incidence?
Incidence is a vertext edge pair such that the vertex is an endpoint of the edge.
An edge is indicent on a vertex if the vertex is one of the edge’s endpoints.
What is the degree of a vertex?
The degree of a vertex v is the number of incident edges on v.
Denoted deg(v)
What is it called when deg(v) = 0
v is an isolated vertex.
A graph can consist of entirely isolated vertices.
What is it called when two or more edges connecting the same 2 vertices?
Parallel, multiple edges, adjacent edges, and multiple adjacency.
Graphs containing these are called a multi-graph.
What is it called when an edge connects a vertex to itself?
It is called a self loop. A graph containing these loops is called a pseudograph.
What is a simple graph?
A simple graph contains no loops or parallel edges.
What is it called when an edge has an associated weight that measures the cost of traversing it.
It is called a weighted graph.
On diagrams, edges are labeled with their weights.
The weights need to be positive or real.
What is a path?
How do we measure an unweighted path length.
How about a weighted path length?
A path is a sequence of vertices connected by edges.
The unweighted path length is the number of edges on the path.
The weighted path length is the sum of costs of edges on the path.
What is a simple path?
What is a circuit?
What is a simple cycle?
In a simple path, each vertex occurs only once in the sequence.
In a circuit (cycle) is a path that begins and ends at the same vertex and no edges are repeated.
A simple cycle is a circuit where all vertices (except the first and the last) are different.
What happens in a connected graph?
There is a path between every pair of distinct vertices.
