Questions and Answers
What does the in-degree of a vertex represent in a directed graph?
In the directed graph defined by edges E = {(A, B), (A, C), (B, C), (C, D)}, what is the out-degree of vertex A?
What is the handshaking theorem primarily used for?
What does the maximum degree represent in a graph?
Signup and view all the answers
Given a directed graph, if vertex D has an in-degree of 2, how many edges must be connected to D?
Signup and view all the answers
If the degree sequence of a directed graph is given as {4, 3, 2, 1}, which statement is true?
Signup and view all the answers
How is the degree sequence arranged for a graph?
Signup and view all the answers
Which of the following statements is NOT true about directed graphs?
Signup and view all the answers
What feature characterizes a directed graph?
Signup and view all the answers
What is the maximum number of edges allowed between two vertices in a simple directed graph?
Signup and view all the answers
Which statement about loops in directed graphs is true?
Signup and view all the answers
In a directed graph with edge multiplicity, what does it mean if an edge has multiplicity m?
Signup and view all the answers
What distinguishes undirected graphs from directed graphs?
Signup and view all the answers
Which condition is NOT present in a simple directed graph?
Signup and view all the answers
In a directed graph with the vertices A, B, C, and D, if there is an edge from A to B and another from B to A, what type of edge is this?
Signup and view all the answers
If a graph contains vertices A, B, and C where A has edges to both B and C, what type of graph does this describe?
Signup and view all the answers
What is the term used for two vertices that share an edge in an undirected graph?
Signup and view all the answers
In an undirected graph, how does a loop affect the degree of a vertex?
Signup and view all the answers
If vertex A has edges (A, B) and (A, D), what is the degree of vertex A in an undirected graph?
Signup and view all the answers
In a directed graph, if there is an edge (u, v), how are u and v described in relation to each other?
Signup and view all the answers
What is the correct way to denote the degree of a vertex v in a graph?
Signup and view all the answers
Which statement is true regarding edges in an undirected graph?
Signup and view all the answers
If a graph consists of the vertices A, B, C, and D with edges {(A, B), (B, C), (C, D)}, how many edges are considered as incident to vertex B?
Signup and view all the answers
Which of the following describes a scenario where vertices A and C are adjacent in a directed graph?
Signup and view all the answers
Study Notes
Basic Terminology
- Degree of a vertex in an undirected graph counts the number of edges incident to it; loops at the vertex contribute twice to the degree.
- Denoted as deg(v) for a vertex v.
Vertex Degree Examples
- In a graph with vertices P, Q, R, and S:
- deg(P) = 2
- deg(Q) = 3
- deg(R) = 2
- deg(S) = 1
Adjacent Vertices
- Two vertices u and v are adjacent if they share an edge e.
- An edge e connects u and v; u is the initial vertex and v is the terminal vertex.
- For loops, the initial and terminal vertices are the same.
Directed Graphs
- In directed graphs, if there is an edge (u, v), then u is adjacent to v and v is adjacent from u.
Edge Multiplicity
- If m different edges connect the same unordered pair of vertices {u, v}, it's referred to as an edge of multiplicity m.
Self-Connecting Edges
- Loops represent edges connecting a vertex to itself, important for modeling networks, e.g. communications links.
Directed Graph Characteristics
- Directed graphs consist of vertices and directed edges (arcs) with arrows indicating the direction.
- Can contain loops, multiple edges, and bidirectional edges.
Simple Directed Graph
- A simple directed graph has no loops or multiple edges; at most one edge exists between any two vertices.
- An edge of multiplicity m is considered if m directed edges exist between vertices (u, v).
In-Degree and Out-Degree
- In a directed graph, in-degree (deg⁻(v)) counts edges leading to vertex v, while out-degree (deg⁺(v)) counts edges originating from vertex v.
- Loops contribute 1 to both in-degree and out-degree of the vertex.
Degree Sequence
- The degree sequence arranges vertex degrees in non-increasing order.
- In directed graphs, both in-degrees and out-degrees are considered.
Example of Degree Sequence
- For the graph G with vertices {A, B, C, D} and edges {(A, B), (A, C), (B, C), (C, D)}:
- Degree sequence in non-increasing order: {3, 2, 2, 1}
- Minimum degree is the smallest degree of any vertex; maximum degree is the largest.
Theorems
- For directed graphs, the total degree sum equals the number of directed edges:
- ∑ deg(v) = |E|
- Handshaking Theorem for undirected graphs states the sum of all vertex degrees equals twice the number of edges:
- ∑ deg(v) = 2m, applicable even with multiple edges and loops.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
Description
This quiz covers the basic terminology of graph theory, focusing on key concepts like the degree of a vertex and its significance in undirected graphs. Test your knowledge of how relationships in a graph can be represented and analyzed. Perfect for those studying introductory graph theory concepts.
