ch1 Flashcards
What is the degree of a vertex in a graph?
The number of edges incident to the vertex.
How do you calculate the total degree of a graph?
Sum all vertex degrees; the result is twice the number of edges.
What is the in-degree of a vertex in a directed graph?
The number of edges directed toward the vertex.
What is the out-degree of a vertex in a directed graph?
The number of edges directed away from the vertex.
State the Handshaking Theorem.
In any undirected graph, the sum of all vertex degrees is twice the number of edges.
What is a source vertex in a directed graph?
A vertex with in-degree 0 and at least one outgoing edge.
What is a sink vertex in a directed graph?
A vertex with out-degree 0 and at least one incoming edge.
What does the Handshaking Theorem tell us about odd-degree vertices?
The number of vertices with an odd degree must be even.
What is the first step in drawing a graph from a degree sequence?
Check if the sum of degrees is even (Handshaking Theorem).
What is the second step in drawing a graph from a degree sequence?
Sort degrees in descending order and connect the highest-degree nodes first.
What is the Havel-Hakimi algorithm used for?
Checking if a degree sequence is graphical and constructing the graph.
What happens if you try to construct a graph and run out of connections early?
The sequence is not graphical; restart with a different approach.
What is a simple graph?
A graph with no loops or multiple edges.
What is a multigraph?
A graph that allows multiple edges between the same pair of vertices but no loops.
What is a pseudograph?
A graph that allows both multiple edges and loops.
What is an isolated vertex?
A vertex with a degree of 0 (no edges connected to it).
What is a pendant vertex?
A vertex with degree 1 (only one edge connected to it).
What is a directed graph?
A graph where edges have directions (arrows).
What is an undirected graph?
A graph where edges have no directions.
What is a connected graph?
A graph where there is a path between every pair of vertices.
What is a disconnected graph?
A graph where at least one pair of vertices is not connected by a path.
What is a spanning subgraph?
A subgraph that contains all the vertices of the original graph but not necessarily all the edges.
What is a bipartite graph?
A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other set.
What is an Eulerian graph?
A connected graph where all vertices have an even degree, allowing for an Eulerian circuit.
