Graphs and Networks Flashcards
What is a connected graph?
each vertex is connected to all other vertices either directly or indirectly
What is a bridge?
An edge that if removed, leaves the graph disconnected
What are isomorphic graphs?
Graphs that are equivalent to each other
What are planar graphs?
Graphs that can be drawn so no edges cross
What are subgraphs?
contains parts of original graph but missing some vertices or edges, any remaining edges are still connected same way
What are simple graphs?
contains no loops or multiple edges between vertices
What are complete graphs?
each vertex is connected once to every other vertices (e=v(v-1)/2)
What are cycles?
• closed path
• start and finish at same vertex
• no repeated edges
no other repeated vertices
What is a tree?
Connected graph with no loops or cycles
e=v-1
Recall Euler’s formula and what it is used for.
v+f-e=2
It expresses the relationship between vertices, edges and faces
What is a bipartite graph?
Graph whose vertices are split into two groups, with each of graph’s edges joining one vertex in one group to a vertex in the other group
What is a directed graph (digraph)?
Contains vertices joined by directed edges or arcs (arrows)
What is a walk?
Repeat edges, repeat vertices, open ->start and finish at different vertices, closed-> start and finish at same vertex, may not include all edges or vertices
What is a trail?
no repeated edges, repeat vertices, open-> start and finish at different vertices (Semi-Eulerian - use all edges), closed -> start and finish at same vertex (Eulerian - use all edges)
What is a path?
• no repeated edges • no repeated vertices (except starting vertex) • Open • start and finish at different vertices • Semi-Hamiltonian - use all vertices • Closed • start and finish at same vertex Hamiltonian - use all vertices
