Graphs Flashcards
What is a Graph?
A graph is a way of representing relationships that exist between pairs of objects.
What is a Graph viewed abstractly?
Viewed abstractly, a graph G is simply a set V of vertices and a collection E of pairs of vertices from V, called edges.
When is an Edge (u, v) Directed?
An edge (u,v) is said to be directed from u to v if the pair (u,v) is ordered, with u preceding v.
When are two vertices said to be Adjacent?
Two vertices u and v are said to be adjacent if there is an edge whose end vertices are u and v.
When is an edge said to be Incident to a vertex?
An edge is said to be incident to a vertex if the vertex is one of the edge’s endpoints.
What are the outgoing edges of a vertex?
The outgoing edges of a vertex are the directed edges whose origin is that vertex.
What are the incoming edges of a vertex?
The incoming edges of a vertex are the directed edges whose destination is that vertex.
What is the degree of a vertex?
The degree of a vertex v, denoted deg(v), is the number of incident edges of v.
