Graph Theory Flashcards
(18 cards)
What is a path
A trail where no node is visited more than once.
What is a trail
A walk where no edge is traversed more than once
What is a cycle
A set of edges that form a pathway where you start and finish at the same node
What is a Hamiltonian cycle
A cycle that visits every vertex exactly once
What is an isomorphic graph
Graphs that are structurally the same but appear different
What is a simple graph
A graph with no loops or multiple edges
What is a complete graph
A graph where every node is directly connected to every other by an edge
What is the equation to find the n.o edges in a complete graph (Kn)
1/2n(n-1)
What is a tree
A simply connected graph that uses the least number of edges
What is a network
A graph with weighted edges
What is a connected graph
A graph where every node is connected to every other node directly or indirectly
What is a bipartite graph
A graph with distinct sets of nodes that can connect to nodes in another set but not with nodes that are part of their own set
What is a connected bipartite graph
A bipartite graph where every node from one set is connected to every node in the
Other set but not to members of its own set
What is an eulerian graph
A graph where every node has an even order
What is a semi eulerian graph
A graph where there are exactly two nodes of odd order
What is a planar graph
A graph where no two edges meet except at a node.
What is euler’s handshake lemma
The sun off all the node orders in a graph = 2 x the n.o edges
What is a spanning tree
A tree that is a subgraph contains all the nodes of the original graph
