Podcast
Questions and Answers
A graph with no ______ or multiple edges is called a simple graph.
A graph with no ______ or multiple edges is called a simple graph.
loops
Two vertices are ______ if they are the endpoints of an edge.
Two vertices are ______ if they are the endpoints of an edge.
adjacent
A graph that has an empty vertex and edge set is called a ______ graph.
A graph that has an empty vertex and edge set is called a ______ graph.
null
The minimum number of colors needed to color the vertices of a graph is called the ______ number.
The minimum number of colors needed to color the vertices of a graph is called the ______ number.
A sequence of distinct vertices is called a ______.
A sequence of distinct vertices is called a ______.
A closed ______ in a graph is called a cycle.
A closed ______ in a graph is called a cycle.
A graph with vertex degrees all ______ is called an even graph.
A graph with vertex degrees all ______ is called an even graph.
A ______ is a list of vertices and edges in a graph.
A ______ is a list of vertices and edges in a graph.
A graph with an ______ path or circuit has a path that uses every edge exactly once.
A graph with an ______ path or circuit has a path that uses every edge exactly once.
The ______ of a graph is the length of the shortest cycle in a graph.
The ______ of a graph is the length of the shortest cycle in a graph.
A ______ graph is a simple graph whose vertices are pairwise adjacent.
A ______ graph is a simple graph whose vertices are pairwise adjacent.
Flashcards are hidden until you start studying
Study Notes
Graph Basics
- A vertex is a region or object in a graph.
- An edge is a path bridge between regions or a relation between objects in a graph.
- The order of a graph is the number of vertices it has.
- The size of a graph is the number of edges it has.
Edge Characteristics
- A loop is an edge whose endpoints are equal.
- Multiple edges are edges that have the same pair of endpoints.
- A graph is simple if it has no loops or multiple edges.
Vertex Relationships
- Two vertices are adjacent or neighbors if they are the endpoints of an edge.
- A click is a set of pairwise adjacent vertices.
- An independent set is a set of pairwise non-adjacent vertices.
Graph Types
- A finite graph is a graph that has a finite vertex and edge set.
- A null graph is a graph that has an empty vertex and edge set.
- Equivalent graphs are graphs where edges form the same connections of vertices in each graph.
- A bipartite graph is a union of two disjoint independence sets.
Graph Properties
- The chromatic number is the minimum number of colors needed to color the vertices of a graph.
- A path is a sequence of distinct vertices.
- A cycle is a closed path in a graph.
- A graph is connected if there exists at least one path between two vertices.
- A graph is disconnected if there is no path between two vertices.
Vertex Properties
- The degree of a vertex is the number of edges incident upon it.
Special Graphs
- A complete graph is a simple graph whose vertices are pairwise adjacent.
- A complete bipartite graph is a graph where two vertices are adjacent if and only if they are in different partite sets.
- The girth of a graph is the length of the shortest cycle.
Graph Traversal
- A walk is a list of vertices and edges in a graph.
- A trail is a walk in a graph with no repeated edges.
- An even graph is a graph with vertex degrees all even.
- An odd vertex is a vertex whose degree is odd in a graph.
- A graph is traversable if there are no repeating edges.
Eulerian and Hamiltonian Graphs
- A graph is Eulerian if it has an Euler path or circuit.
- A graph is Hamiltonian if a Hamiltonian path passes through all vertices at once.
- An Eulerian circuit is a circuit or trail containing all the edges in a graph.
- An Euler path is a path that uses every edge of a graph exactly once.
Studying That Suits You
Use AI to generate personalized quizzes and flashcards to suit your learning preferences.
