Graph Theory, Walks/Trails etc.., Trees Flashcards
What is a Graph?
A graph 𝐺 is a non-empty set of vertices 𝑉 𝐺 and a (possibly empty) set of edges 𝐸(𝐺), where each edge is associated with a set consisting of either one or two vertices.
Describe Edges and Vertices in a basic fashion.
Vertices: Dots
Edges: Lines joining two dots, or joining a dot to itself
What is the Degree of a Vertex?
The degree of a vertex is the number of edges incident with it.
What makes a graph Simple
A graph is simple if it has no loops and no multiple edges.
What is the Handshake Theorem?
The Handshake Theorem says that the sum of the degrees of a graph is twice the number of edges. (Each Edge contributes to 2 degrees… One at the start, one at the finish. Don’t overthink it)
By the handshake theorem, every graph has an even number of vertices of odd degree
When is a Graph, ‘Connected’
A graph is connected if and only if there is a walk from any given vertex to any other given vertex.
What is a ‘Walk’
A walk is a finite or infinite sequence of edges which joins a sequence of vertices. It is defined by the following properties:
1. It can start and end at any vertex.
2. It can traverse each edge and vertex any number of times.
3. Each consecutive pair of edges in the sequence shares a common vertex.
A walk on a graph is essentially an ordered list of vertices and edges which “takes you” from a starting vertex to an end vertex. Essentially, it just describes a path you can take along the edges of a graph.
Let 𝐺 be a connected graph. Then 𝐺 has an Euler circuit if and only if every vertex of 𝐺..?
𝐺 has an Euler circuit if and only if every vertex of 𝐺 has even degree.
What is a trail in graph theory?
A trail is a walk in a graph where all edges are distinct; no edge is repeated. It allows revisiting vertices but not edges.
A trail is just a walk where you don’t go back along any edges.
What is a circuit in graph theory?
A circuit is a closed trail where the starting and ending vertices are the same. It traverses through edges with no repetition, and returns to the original vertex.
A circuit is just a trail which starts and ends at the same vertex.
What is an Euler circuit in graph theory?
An Euler circuit is a circuit that uses every edge of a graph exactly once. For a graph to have an Euler circuit, it must be connected and every vertex must have an even degree.
An Euler circuit is a circuit where you include every edge exactly once.
In a circuit, can vertices be repeated?
Yes, in a circuit, vertices can be repeated, but each edge must be used exactly once. The only requirement for a circuit is that it starts and ends at the same vertex and does not repeat any edges.
A graph G, with n vertices, is a tree iff..?
A graph G, with n vertices, is a tree iff it is
* Simple
* Connected
* Has n-1 edges (One less edge than vertices)
Every vertex of a tree with 15 edges has either degree 3 or degree 1. How many vertices of the tree have degree 3?
- Total vertices = 16
- Let x be vertices degree 1, and y be vertices degree 3
- thus x + y = 16 and,
- x + 3y = 30 (30 is total degree. Handshake: 15 edges, 2 per edge)
- From these 2 equations we can see 2y = 14, Thus y = 7
- Thus x = 9 (x + 7 = 16)
What is a trail where every edge has been included exactly once?
A Euler Trail
What is an adjacency matrix for a graph?
An adjacency matrix A for a graph G tells us which vertices are connected by an edge, where
