CH7: NETWORKS [VOCAB] Flashcards
nodes/vertices
points on a network
edge
a line joining to nodes or vertices
faces/regions
edges divide a graph up into seperate sections
loop
an edge that starts and ends at the same vertex
multiple edges
two or more edges that connect the same two vertices
weighted graph/network
graphs that have amounts or distances or some information on each edge
directed edges/arcs
an edge with significant direction shown with an arrow
directed graph/network or digraph
any graph involving directed edges (1 or more)
undirected graph/network
any graph with no directed edges
simple graph/network
a graph or network with no loops, multiple edges or direction, no crossovers
walk
a sequence of edges joined by vertices
open walk
a walk which does not start and end at the same vertex
closed walk
a walk which starts and ends at the same vertex
open path
a walk that has no repeats of edges or vertices and does not start and end at the same vertex
closed path or ‘cycle’
a walk that has no repeats of edges or vertices and starts and ends at the same vertex
path length
the number of edges a walk, path or cycle uses
trail
a walk with no repeated edges (may have repeated vertices)
connected graph
an undirected graph where every vertex is connected to each other
disconnected/unconnected graph
a graph where a vertex is not joined by an edge
complete graphs
simple graphs in which every vertex is connected to every other
bridge
any edge which, when removed, causes a network to become disconnected
degree/order
the number of edges that meet a vertex
isolated vertex
a vertex not connected to an edge
planar graphs
networks that can be drawn without edges crossing over
null graphs
networks made up of no edges, just isolated vertices
trivial graphs
networks that have only one vertex (null graphs)
subgraph
a smaller section of the original graph
platonic solid
the ‘net’ of a 3D shape where each face is the same regular polygon
traversable
refers to a connected graph with 0 odd vertices or exactly 2 odd vertices
eulerian trail
travels every edge once, may repeat vertices, 0 odd vertices, starts and finishes at the same vertex
semi-eulerian
- connected graph
- open trail
- includes every edge only once
- contains 2 odd vertices
- starts and finishes at the same point
adjacent vertices
vertices that share a common edge
in-degree
number of edges coming into a vertex
out-degree
number of edges coming out of a vertex
bipartite graph
a graph in which the vertices can be split into two groups
complete bipartite graph
a bipartite graph that has every member of one group connected to every member of the other group
euler’s formula
v + f - e = 2
circuit
a closed trail. a trail that starts and ends at the same vertex.
path
a walk if it includes no repeated use of an edge and no repeated use of a vertex, (except for the vertex we started from)
0 odd vertices
.
2 odd vertices
.
hamiltonian path
path that cuts through every vertex
hamiltonian cycle
type of hamiltonian graph that starts and ends at the same vertex
semi-hamiltonian graph
.
