Discrete: The language of graphs Flashcards
Definition of a Vertex
a vertex is shown as a point on a graph
Definition of an Edge
an edge is a line or curve with a vertex at each end
Definition of a Walk
a walk is a set of edges joined end to end
Definition of a Trail
a trail is a walk in which no edges are repeated
Definition of a Cycle
a cycle is a trail that starts and finishes at the same vertex
Definition of Adjacent vertices
vertices are adjacent if there is an edge with these vertices at its ends
Definition of a connected graph
a graph is connected if it is possible to get from any vertex to another, either directly or indirectly
Definition of a loop
a loop is an edge that directly connects a vertex to itself
When does a graph have multiple edges?
a graph has multiple edges if there are two or more edges that directly connect the same pair of vertices
What is a simple graph?
a simple graph is a graph with no loops and no multiple edges
Definition of a degree of a vertex
the degree of a vertex is the number of edges that end at that vertex
What is a subgraph?
a subgraph is a graph contained within another graph
Definition of subdivision
subdivision is inserting a vertex of degree 2 into an edge
What is a Bipartite graph?
a bipartite graph is a simple graph that can be partitioned into two sets: no edge connects two vertices in the same set
What is a complete Bipartite graph?
a complete bipartite graph is a simple bipartite graph with the maximum possible number of edges
What is an Adjacency matrix?
an adjacency matrix shows the number of edges that directly connect each pair of vertices
Definition of a complement?
the complement of a simple graph is the set of edges that, when added to the graph, makes a complete graph
What is a simple-connected graph?
a simple-connected graph is a graph that is simple and connected
What is a tree?
a tree is a simple-connected graph with the minimum possible number of edges
What is a transversible graph?
a transversible graph can be drawn as a trail without going over the same edge twice
What is a Eulerian graph?
a eulerian graph is a connected graph that has no vertices of odd degree
What is a semi-eulerian graph?
a semi-eulerian graph is a connected graph that has exactly two vertices of odd degree
What is a Hamiltonian graph?
a Hamiltonian graph is a graph that contains a cycle that passes through every vertex exactly once: apart from starting and finishing at the same vertex
