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
