1/32
This is called a graph
Name | Mastery | Learn | Test | Matching | Spaced |
---|
No study sessions yet.
Digraph
A directed graph
Simple
Undirected
Unweighted
No arcs
No loops
Arc
Two edges connect two vertices
Closed Walk
Starts and ends at the same vertex (eg. A-B-A)
Open Walk
Starts and ends at different vertices (eg. A-B-C)
Path
Walk with no repeat edges or vertices
Closed Path
Walk that repeats no edges or vertices except the initial vertex, ends at initial vertex (eg. A-B-C-D-A)
Open Path
Walk with no repeat edges or vertices, must end at a different place to starting (eg. A-B-C)
Length
Amount of edges crossed
Trail
A walk with no repeated edges but vertices can be repeated. Can be open or closed
Connected
When undirected, if two vertices are joined by any combination of edges
Strongly connected
Each vertex is connected there and back
Weakly connected
Directed graph in which, if undirected, graph would be connected, but direction means some points cannot be reached by path from other vertex
Complete Graph
Simple
Connected to every other vertex
No multiple edges
Adjacent Vertices
Vertices directly joined by an edge
Bridge
An edge in a connected graph that, if removed, would make the graph disconnected
Planar
Can be drawn in the 2-d plane without crosses
Euler’s Rule
V + F = E + 2
Subgraph
A selection of vertices and edges of a larger graph
Tree
Connected graph with no cycles
Cycle
Closed path
Bipartite Graph
Can be split into two groups where every edge connects from one group to another, and no edge connects within a group
Complete bipartite graph
When every vertex in one group connects to all of the vertices in the other group
A complete bipartite graph is
not a complete graph
Degree/ Order
If undirected, the number of edges connected to a vertex
Odd vertex
A vertex with an odd degree
Even vertex
A vertex with an even degree
In degree
Connected into a vertice
Out degree
Directed from a vertice
Eulerian Trail
A closed trail with no odd vertices
Semi-eulerian trail
An open trail with exactly two odd-degree vertices
Hamiltonian Path
A closed path that visits every vertex only once and uses no edge more than once
Semi-hamiltonian path
An open path that visits every vertex only once and uses no edge more than once