Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
Appendix B - Sets, Etc.
| set | a collection of distinguishable objects, called its members or elements.
(See page 1070)
|
 |
|
|
| empty set | denoted ø, it is the set containing no members.
(See page 1070)
|
|
|
|
| integers | denoted Z it is the set {...,-2,-1,0,1,2,...}.
(See page 1070)
|
|
|
|
| real numbers | denoted R
(See page 1070)
|
|
|
|
| natural numbers | denoted N, it is the set {0,1,2,...}.
(See page 1070)
|
|
|
|
| subset | If all the elements of a set A are contained in a set B, that is, if x ∈ A implies x ∈ B, then we write A ⊆ B and say that A is a subset of B.
(See page 1071)
|
|
|
|
| proper subset | A set A is a proper subset of B, written A ⊂ B, if A ⊆ B but A ≠ B.
(See page 1071)
|
|
|
|
| intersection | of sets A and B is the set A ∩ B = {x : x ∈ A and x ∈ B}.
(See page 1071)
|
|
|
|
| union | of sets A and B is the set A ∪ B = {x : x ∈ A or x ∈ B}.
(See page 1071)
|
|
|
|
| difference | between two sets A and B is the set A - B = {x : x ∈ A and x ∉ B}.
(See page 1071)
|
|
|
|
| Venn diagram | a graphical picture in which sets are represented as regions of the plane.
(See page 1072)
|
|
|
|
| universe | All the sets under consideration are subsets of some larger set U called the universe.
(See page 1072)
|
|
|
|
| disjoint | Two sets A and B are disjoint if they have no elements in common, that is, if A ∩ B = ø.
(See page 1073)
|
|
|
|
| cardinality | number of elements in a set, denoted |S|.
(See page 1073)
|
|
|
|
| finite | If the cardinality of a set is a natural number, we say the set is finite; otherwise, it is infinite.
(See page 1073)
|
|
|
|
| countably infinite | An infinite set that can be put into a one-to-one correspondence with the natural numbers N is countably infinite; otherwise, it is uncountable.
(See page 1073)
|
|
|
|
| n-set | sometimes used to denote a finite set of n elements.
(See page 1073)
|
|
|
|
| singleton | a 1-set
(See page 1073)
|
|
|
|
| k-subset | sometimes used to denote a subset of k elements of a set
(See page 1073)
|
|
|
|
| power set | The set of all subsets of a set S, including the empty set and S itself, denoted 2S.
(See page 1073)
|
|
|
|
| ordered pair | of two elements a and b is denoted (a, b) and can be defined formally as the set (a, b) = {a, {a,b}}.
(See page 1073)
|
|
|
|
| binary relation | R on two sets A and B is a subset of the Cartesian product A x B.
(See page 1075)
|
|
|
|
| reflexive | A binary relation R ⊆ A x A is reflexive if a R a for all a, b ∈ A.
(See page 1075)
|
|
|
|
| symmetric | The relation R is symmetric if a R b implies b R a for all a, b ∈ A.
(See page 1075)
|
|
|
|
| transitive | The relation R is transitive if a R b and b R c imply a R c for all a, b, c ∈ A.
(See page 1075)
|
|
|
|
| equivalence relation | A relation that is reflexive, symmetric, and transitive.
(See page 1075)
|
|
|
|
| equivalence class | If R is an equivalence relation on a set A, then for a ∈ A, the equivalence class of a is the set [a] = {b ∈ A : a R b}, that is, the set of all elements equivalent to a.
(See page 1075)
|
|
|
|
| partial order | A relation that is reflexive, antisymmetric, and transitive.
(See page 1076)
|
|
|
|
| antisymmetric | A binary relation R on a set A is antisymmetric if a R b and b R a imply a = b.
(See page 1076)
|
|
|
|
| partially ordered set | a set on which a partial order is defined
(See page 1076)
|
|
|
|
| maximal | There may be several maximal elements a such that for no b ∈ A, where b ≠ a, it is the case that a R b.
(See page 1076)
|
|
|
|
| total or linear order | A partial order R on a set A is a total or linear order if for all a, b ∈ A, we have a R b or b R a, that is, if every pairing of elements of A can be related by R.
(See page 1077)
|
|
|
|
| function | Given two sets A and B, a function f is a binary relation on A x B such that for all a ∈ A, there exists precisely one b ∈ B such that (a, b) ∈ f. The set A is called the domain of f, and the set B is called the codomain of f.
(See page 1077)
|
|
|
|
| argument | Given a function f : A → B, if b = f(a), we say that a is the argument of f and that b is the value of f at a. We also call each ai an argument to the function f, though technically the (single) argument to f is the n-tuple (a1, a2, . . . , an).
(See page 1078)
|
|
|
|
| equal | Two functions f and g are equal if they have the same domain and codomain and if, for all a in the domain, f(a) = g(a).
(See page 1078)
|
|
|
|
| finite sequence | of length n is a function f whose domain is the set of n integers
{0, 1, . . . , n - 1}.
(See page 1078)
|
|
|
|
| image | If f : A → B is a function and b = f(a), then we sometimes say that b is the image of a under f.
(See page 1078)
|
|
|
|
| range | of f is the image of its domain, that is, f(A).
(See page 1078)
|
|
|
|
| surjection | A function is a surjection if its range is its codomain.
(See page 1078)
|
|
|
|
| injection | A function f : A → B is an injection if distinct arguments to f produce distinct values, that is, if a ≠ a′ implies f(a) ≠ f(a′).
(See page 1079)
|
|
|
|
| one-to-one | An injection is sometimes called a one-to-one function.
(See page 1079)
|
|
|
|
| bijection | A function f : A → B is a bijection if it is injective and surjective.
(See page 1079)
|
|
|
|
| one-to-one correspondence | A bijection is sometimes called a one-to-one correspondence, since it pairs elements in the domain and codomain.
(See page 1079)
|
|
|
|
| permutation | A bijection from a set A to itself.
(See page 1079)
|
|
|
|
| inverse | When a function f is bijective, its inverse f-1 is defined as f-1(b) = a if and only if f(a) = b.
(See page 1079)
|
|
|
|
| directed graph | (or digraph) G is a pair (V, E), where V is a finite set and E if a binary relation on V.
(See page 1080)
|
|
|
|
| vertex set | The set V is called the vertex set of G, and its elements are called vertices (singular: vertex).
(See page 1080)
|
|
|
|
| edge set | The set E is called the edge set of G, and its elements are called edges.
(See page 1080)
|
|
|
|
| self-loops | edges from a vertex to itself.
(See page 1080)
|
|
|
|
| undirected graph | In an undirected graph G = (V, E), the edge set E consists of unordered pairs of vertices, rather than ordered pairs.
(See page 1080)
|
|
|
|
| incident from | If (u, v) is an edge in a directed graph G = (V, E), we say that (u, v) is incident from or leaves vertex u and is indident to or enters vertex v.
(See page 1080)
|
|
|
|
| incident on | If (u, v) is an edge in an undirected graph G = (V, E), we say that (u, v) is incident on vertices u and v.
(See page 1080)
|
|
|
|
| adjacent | If (u, v) is an edge in a graph G = (V, E), we say that vertex v is adjacent to vertex u.
(See page 1080)
|
|
|
|
| degree | of a vertex in an undirected graph is the number of edges incident on it. The number of children of a node x in a rooted tree T is called the degree of x. Notice that the degree of a node depends on whether T is considered to be a rooted tree or a free tree. The degree of a vertex in a free tree is, as in any undirected graph, the number of adjacent vertices. In a rooted tree, however, the degree is the number of children - the parent of a node does not count toward its degree.
(See pages 1081, 1088)
|
|
|
|
| isolated | a vertex whose degree is 0
(See page 1081)
|
|
|
|
| out-degree | of a vertex in a directed graph is the number of edges leaving it.
(See page 1081)
|
|
|
|
| in-degree | of a vertex in a directed graph is the number of edges entering it.
(See page 1081)
|
|
|
|
| degree | of a vertex in a directed graph is its in-degree plus its out-degree.
(See page 1081)
|
|
|
|
| path | of length k from a vertex u to a vertex u′ in a graph G = (V, E) is a sequence ⟨v0, v1, v2, . . . , vk⟩ of vertices such that u = v0, u′ = vk, and (vi-1, vi) ∈ E for i = 1, 2, . . . , k. The length of the path is the number of edges in the path.
(See page 1081)
|
|
|
|
| contains | The path contains the vertices v0, v1, . . . , vk and the edges
(v0, v1), (v1, v2), . . . , (vk-1, vk).
(See page 1081)
|
|
|
|
| simple | A path is simple if all vertices in the path are distinct. A cycle is simple if, in addition, v1, v2, . . . , vk are distinct. A directed graph with no self-loops is simple.
(See page 1081, 1082)
|
|
|
|
| subpath | of path p = ⟨v0, v1, . . . , vk⟩ is a contiguous subsequence of its vertices. That is, for any 0 ≤ i ≤ j ≤ k, the subsequence of vertices ⟨vi, vi+1, . . . , vj⟩ is a subpath of p.
(See page 1081)
|
|
|
|
| cycle | In a directed graph, a path ⟨v0, v1, . . . , vk⟩ forms a cycle if v0 = vk and the path contains at least one edge. In an undirected graph, a path ⟨v0, v1, . . . , vk⟩ forms a (simple) cycle if k ≥ 3, v0 = vk, and v1, v2, . . . , vk are distinct.
(See pages 1081, 1082)
|
|
|
|
| acyclic | A graph with no cycles is acyclic.
(See page 1082)
|
|
|
|
| connected | property of an undirected graph if every pair of vertices is connected by a path.
(See page 1082)
|
|
|
|
| connected components | of a graph are the equivalence classes of vertices under the "is reachable from" relation.
(See page 1082)
|
|
|
|
| strongly connected | property of a directed graph if every two vertices are reachable from each other.
(See page 1082)
|
|
|
|
| strongly connected components | of a directed graph are the equivalence classes of vertices under the "are mutually reachable" relation. A directed graph is strongly connected if it has only one strongly connected component.
(See page 1082)
|
|
|
|
| isomorphic | Two graphs G = (V, E) and G′ = (V′, V′) are isomorphic if there exists a bijection f : V → V′ such that (u, v) ∈ E if and only if (f(u), f(v)) ∈ E′. In other words, we can relabel the vertices of G to be vertices of G′, maintainting the corresponding edges in G and G′.
(See page 1082)
|
|
|
|
| subgraph | A graph G′ = (V′, E′) is a subgraph of G = (V, E) if V′ ⊆ V and E′ ⊆ E.
(See page 1082)
|
|
|
|
| induced | Given a set V′ ⊆ V, the subgraph of G induced by V′ is the graph
G′ = (V′, E′), whereE′ = {(u, v) ∈ E : u, v ∈ V′}.
(See page 1082)
|
|
|
|
| directed version | Given an undirected graph G = (V, E), the directed version of G is the directed graph G′ = (V, E′), where (u, v) ∈ E′ if and only if (u, v) ∈ E. That is, each undirected edge (u, v) in G is replaced in the directed version by the two directed edges (u, v) and (v, u).
(See page 1082)
|
|
|
|
| undirected version | Given a directed graph G = (V, E), the undirected version of G is the undirected graph G′ = (V, E′), where (u, v) ∈ E′ if and only if u ≠ v and (u, v) ∈ E. That is, the undirected version contains the edges of G "with their directions removed" and with self-loops eliminated.
(See page 1082)
|
|
|
|
| neighbor | In a directed graph G = (V, E), a neighbor of a vertex u is any vertex that is adjacent to u in the undirected version of G. That is, v is a neighbor of u if either (u, v) ∈ E or (v, u) ∈ E. In an undirected graph, u and v are neighbors if they are adjacent.
(See page 1083)
|
|
|
|
| complete graph | is an undirected graph in which every pair of vertices is adjacent.
(See page 1083)
|
|
|
|
| bipartite graph | is an undirected graph G = (V, E) in which V can be partitioned into two sets V1 and V2 such that (u, v) ∈ E implies either u ∈ V1 and v ∈ V2 or
u ∈ V2 and v ∈ V1. That is, all edges go between the two sets V1 and V2.
(See page 1083)
|
|
|
|
| forest | An acyclic, undirected graph, but possibly disconnected, is a forest.
(See page 1083)
|
|
|
|
| free tree | A connected, acyclic, undirected graph is a (free) tree.
(See page 1083)
|
|
|
|
| dag | directed acyclic graph
(See page 1083)
|
|
|
|
| multigraph | like an undirected graph, but it can have both multiple edges between vertices and self-loops
(See page 1083)
|
|
|
|
| hypergraph | like an undirected graph, but each hyperedge, rather than connecting two vertices, connects an arbitrary subset of vertices.
(See page 1083)
|
|
|
|
| contraction | of an undirected graph G = (V, E) by an edge e = (u, v) is a graph
G′ = (V′, E′), where V′ = V - {u, v} ∪ {x} and x is a new vertex.
(See page 1084)
|
|
|
|
| rooted tree | a free tree in which one of the vertices is distinguished from the others.
(See page 1087)
|
|
|
|
| root | the distinguished vertex of a rooted tree.
(See page 1087)
|
|
|
|
| node | Often used in the graph theory literature as a synonym for "vertex," we shall reserve the term "node" to mean a vertex of a rooted tree.
(See page 1087)
|
|
|
|
| ancestor | Any node y on the unique path from r to x is called an ancestor of x.
(See page 1087)
|
|
|
|
| descendant | If y is an ancestor of x, then x is a descendant of y. (Every node is both an ancestor and a descendant of itself).
(See page 1087)
|
|
|
|
| proper ancestor | If y is an ancestor of x and x ≠ y, then y is a proper ancestor of x and x is a proper descendant of y.
(See page 1087)
|
|
|
|
| subtree rooted at x | the tree induced by descendants of x, rooted at x.
(See page 1087)
|
|
|
|
| parent | If the last edge on the path from the root r of a tree T to a node x is
(y, x), then y is the parent of x, and x is a child of y. The root is the only node in T with no parent.
(See page 1087)
|
|
|
|
| siblings | Two nodes which have the same parent.
(See page 1088)
|
|
|
|
| external node | or leaf. A node with no children.
(See page 1088)
|
|
|
|
| internal node | a nonleaf node
(See page 1088)
|
|
|
|
| depth | The length of the path from the root r to a node x is the depth of x in T.
(See page 1088)
|
|
|
|
| height | of a node in a tree is the number of edges on the longest simple downward path from the node to a leaf, and the height of a tree is the height of its root. The height of a tree is also equal to the largest depth of any node in the tree.
(See page 1088)
|
|
|
|
| ordered tree | a rooted tree in which the children of each node are ordered. That is, if a node has k children, then there is a first child, a second child, . . . , and a kth child.
(See page 1088)
|
|
|
|
| binary tree | T is a structure defined on a finite set of nodes that either- contains no nodes, or
- is composed of three disjoint sets of nodes; a root node, a binary tree called its left subtree, and a binary tree called its right subtree.
(See page 1089)
|
|
|
|
| empty tree | or null tree, sometimes denoted NIL, is the binary tree that contains no nodes.
(See page 1089)
|
|
|
|
| left child | If the left subtree is nonempty, its root is called the left child of the root of the entire tree.
(See page 1089)
|
|
|
|
| right child | The root of a nonnull right subtree is the right child of the root of the entire tree.
(See page 1089)
|
|
|
|
| absent | If a subtree is the null tree NIL, we say that the child is absent or missing. In a positional tree, the ith child of a node is absent if no child is labeled with integer i.
(See pages 1089, 1090)
|
|
|
|
| full binary tree | each node is either a leaf or has degree exactly 2.
(See page 1089)
|
|
|
|
| positional tree | In a positional tree, the children of a node are labeled with distinct positive integers.
(See page 1090)
|
|
|
|
| k-ary | tree is a positional tree in which for every node, all children with labels greater than k are missing. Thus, a binary tree is a k-ary tree with
k = 2.
(See page 1090)
|
|
|
|
| complete k-ary tree | a k-ary tree in which all leaves have the same depth and all internal nodes have degree k.
(See page 1090)
|
|
|
|
| internal path length | of a full binary tree is the sum, taken over all internal nodes of the tree, of the depth of each node.
(See page 1091)
|
|
|
|
| external path length | the sum, taken over all leaves of the tree, of the depth of each leaf.
(See page 1091)
|
|
|
|
| k-coloring | Given an undirected graph G = (V, E), a k-coloring of G is a function
c : V → {0, 1, . . . , k - 1} such that c(u) ≠ c(v) for every edge (u, v) ∈ E. In other words, the numbers 0, 1, . . . , k - 1 represent the k colors, and adjacent vertices must have different colors.
(See page 1091)
|
2002 McGraw-Hill Higher Education