Chapter 2 Flashcards
What is a graph?
A series of points connected by lines
What is a weighted graph
A graph with numbers associated to each edge
What is a vertex/node
A point in a graph
What is an edge/arc
A line segment joining vertices
What is a vertex set
A lost if vertices
What is the edge set
A lost of all the edges
What is a sub graph?
A part of the original graph
What is the degree/order of a vertex?
How many edges are incident to it
What is a walk?
A route through the graph from vertex to the next
What is a path?
A walk where no vertex is visited more than once
What is a trail?
A walk where no edge is visited more than once
What is a cycle
A walk where the end we’re is the same as the start one and no vertex is visited more than once
What is a Hamiltonian cycle?
A cycle which includes ever vertex
When are two vertices connected?
When two vertices are connected
When is. A grain connected?
When all it’s vertices are connected
What is a loop?
An edge which starts and ends at the same vertex
What is a simple graph?
A graph with no loops which is connected
What is a directed graph?
When the edges have a direction
In an undirected graph what is the sum of degrees of the vertices equal to?
2x number if edges
What is euler’s handshaking lemma ?
The number of odd vertices must be even
What is a tree?
A connected graph with no cycles
What is a spanning tree?
A tree which cintains all vertices
What is a complete graph?
A graph where every vertex is direct,y. Connected to each other vertex by a single edge
What is an isomorphic graph?
A graph with the same information which can be drawn differently
