Graphs and networks Flashcards
All the language needed for graphs
Isomorphic
2 graphs that are the same
Bipartite graph
A connected graph with 2 sets of vertices where no connections exist within each set
Degree
The number of edges connected to a vertex
Eulerian
A closed path that covers every edge exactly once
Semi-Eulerian
Has 2 odd vertices and the rest even
Cycle
A closed path
Weight
A network contains this on each edge
Node
A Point on a graph
Arc
The line connecting two points
Complete Graph
A type of graph where every pair of vertices is connected by a single edge
Tree
A connected graph with no cycles
Edge
The line connecting 2 points
Order
The number of edges connected to a vertex
Complement graph
The inverse of a graph. Contains only the edges needed to complete original graph.
Connected graph
A graph where a path exists between any two vertices
Walk
A sequence of edges
Subgraph
Made up of a smaller set of vertices and edges taken from another graph
Planar Graph
A type of graph that can be drawn so that none of the arcs cross
Trail
A walk where none of the edges are repeated
Incidence Matrix
An array describing the relationship between vertices and adjacent edges
Simple graph
A graph with no multiple edges or loops
Adjacency matrix
An array indicating whether pairs of vertices are adjacent or not.
Even Vertices
In a Eulerian graph, we have to have all of them as this
Path
A trail where none of the vertices are repeated
Network
A graph with weighted edges
Subdivision
A graph where edges have been divided by new vertices
Hamiltonian Cycle
Visit each vertex once and return back to the start gives you this.
Regular graph
The order of each of the graphs is the same
