Flashcards in Networks Deck (35):
The junctions and endpoints of a network.
The connections between the vertices.
The separate areas of a network.
Can be drawn without taking the pen off the paper and without going over the same edge twice.
You may pass through the same vertex more than once.
Must be connected and have either 0 odd vertices or 2 odd vertices.
Define weighted graph/weighted network.
When each edge is worth a particular weight.
Eg: distance, cost, time, etc.
Define directed edges/arcs.
An edge that is directed.
Define undirected/non-directed graph.
Any graph having no directed edges.
Define directed graph/digraph.
Any graph involving directed edges.
Define simple graph/simple network.
An undirected, unweighted graph with no loops and no multiple edges.
Define simple directed graph.
A directed graph with no loops or multiple edges.
Define simple weighted graph.
A weighted graph with no loops or multiple edges.
A sequence of vertices in which there is an edge from each vertex to the next.
Define closed walk.
Any walk that starts and finishes at the same vertex.
Define open walk.
Any walk that does not end at the same vertex.
Any walk that has no repeated use of edges or vertices.
Define open path.
Any path that does not end at the same vertex.
Define closed path/cycle.
Any path that starts and finishes at the same vertex.
Define the length of a walk.
The number of edges the walk or path uses.
A walk involving no repeated edges.
Can repeat vertices.
Paths are trails too.
Define adjacent vertices.
Vertices that can be connected by one or more edges.
Define connected vertices.
Vertices connected by only one edge.
Any edge, which when removed, leaves the graph disconnected.
Define complete graphs.
Simple graphs in which every vertex is connected to every other vertex by a single edge.
Define planar graph.
A graph that can be drawn in the plane without its edges crossing over.
Any graph that involves a selection of the vertices and edges from its original graph.
Any simple graph that contains no closed paths/cycles.
Define bipartite graph.
A graph in which the vertices can be split into two groups such that every edge joins a vertex from one group to a vertex from the other group and no edges join vertices from the same group.
Define Eulerian trail.
A trail in a connected graph that travels every edge once and only once, repeated vertices permitted.
Define Eulerian circuit.
A Eulerian trail that starts and finishes at the same vertex.
A traversable graph that starts and finishes at the same vertex.
Define semi-Eulerian trail.
A Eulerian trail that starts and finishes at different vertices.
Define Hamiltonian path.
A path in a graph that visits every vertex in the graph once only with the possible exception of repeating the first vertex at the end.
Define Hamiltonian cycle
A Hamiltonian cycle that starts and finishes at the same vertex.
A connected graph that contains an open Hamiltonian path, but not a Hamiltonian cycle.