Graphs and Networks Flashcards
What is a walk
Any route through a graph
What is a Path
A walk where no vertex is visited multiple times
What is a Trail
A walk where no Edge is visited multiple times
What is a cycle
A path where the end vertex and the start vertex are the same
What is a Hamiltonian cycle
A cycle that includes every vertex
What is a connected graph
A graph where all the nodes are connected either directly or indirectly
What is a simple graph
A graph with no loops and a maximum of 1 vertex connected to each other
How could you calculate sum of the degrees of the vertices
Number of edges *2
What is a tree
A connected graph with no cycles
What is a spanning tree
A subgraph containing all vertices that is also a tree
What is a complete graph
A graph in which every vertex is connected to every other vertex
How would you find the number of vertices in a complete graph
n(n+1) /2
What is a isomorphic graph
A graph which shows the same information in a different format
