CHP 2: Graphs and Networks - Key Terminology Flashcards
Definition of GRAPH
A graph consists of points (called vertices or nodes) which are connected by lines (edges or arcs).
Definition of WEIGHTED GRAPH
When a graph has a number associated with each edge (usually called its weight).
Also called weighted network.
Definition of SUBGRAPH
A graph, each of whose vertices belongs to the original graph and each of whose edges belongs to the original graph. (Part of the original graph)
What is a list of vertices often called?
Vertex Set
What is a list of edges often called?
Edge Set
Definition of DEGREE
Number of edges incident to a vertex. If even it is called an even degree and vice versa for odd.
Definition of VALENCY
Number of edges incident to a vertex. If even it is called an even degree and vice versa for odd.
Definition of ORDER OF A VERTEX
Number of edges incident to a vertex. If even it is called an even degree and vice versa for odd.
Definition of WALK
A walk is a route through a graph along edges from one vertex to the next.
Definition of PATH
A path is a walk in which no vertex is visited more than once.
Definition of CYCLE
A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once.
Definition of HAMILTONIAN CYCLE
A cycle that includes every vertex.
Definition of CONNECTED GRAPH
When all vertices are connected by paths.
Definition of LOOP
A loop is an edge that starts and finishes at the same vertex.
Definition of SIMPLE GRAPH
A graph in which there are no loops and there is at most one edge connecting any pair of vertices.
Definition of DIRECTED EDGE
If edge of graph have a direction associated with them they are a directed edge.
Definition of DIGRAPH
Abbreviation of directed graph and means a graph with directed edges.
Define EULER’S HANDSHAKING LEMMA
In any undirected graph, the sum of the degrees of the vertices is equal to 2 x the number of edges. As a consequence, the number of odd vertices must be even, including possibly zero.
Definition of TREE
A connected graph with no cycles.
Definition of SPANNING TREE
A subgraph which includes all the vertices of the original graph and is also a tree.
Definition of COMPLETE GRAPH
A graph in which every vertex is directly connected by a single edge to each of the other vertices.
Definition of ISOMORPHIC GRAPH
A graph which show the same information but may be drawn differently.
Definition of ADJACENCY MATRIX
Can be used to represent a graph or network and provides information about the connections between the vertices in a graph.
Each entry describes the number of arcs joining the corresponding vertices.
Definition of DISTANCE MATRIX
A matrix associated with a weighted graph.
its entries represent the weight of each arc, not the number of arcs.
