Next: Appendix B: STL Iterator Analysis Up: 4 Applied Concepts Previous: 10. Summary and Outlook

Appendix A: Common Mathematical Terms

Basic mathematical terms are reviewed. The readers' familiarity with sets and subsets [2] is required in the following. All sets which contain only one element (singleton) can be used to describe a vertex.

Definition 44 (Relation)   A relation between sets and is a collection of ordered pairs such that and , if .

Definition 45 (Function)   A function or mapping is a rule that assigns to each element exactly one element . So maps into . This is denoted by .

A permutation of a finite set is usually given by its action on the elements of the set. An example is given by the basic set with a transformation into where the notation states that the permutation maps , and so on. Thereby all permutations of a finite set can be placed into two sets.

Definition 46 (Parity)   A permutation of a finite set can be expressed as either an even or an odd number of transpositions, but not both. In the former case, the permutation is called even, in the latter it is odd.

Definition 47 (Image)   Let and be sets, be the function , and . Then the image of under , denoted by , is the unique member that associates with .

 (11.1)

Definition 48 (Composite Function)   If and are functions with and , then there is a natural function mapping into , the composite function, consisting of followed by . It can be written the composition of functions is denoted by .

Definition 49 (Preimage)   The preimage (fiber, inverse image) of a set under is the subset of defined by

The preimage of a singleton, , is a fiber or a level set. A fiber can also be the empty set . The union set of all fibers of a function is called the total space, E.

Definition 50 (Group)   A group is a set with a binary operation , such that the following axioms are satisfied:
• is associative

• such that for all . The element is an identity element for on .

• , such that . The element is an inverse of with respect to the operation .

Definition 51 (Abelian)   A group is Abelian, if its binary operation is commutative.

Definition 52 (Subgroup)   A subset of a group is a subgroup of if is a group and closed under the operation . The subgroup consists of the identity element of , whereas is the trivial subgroup of . All other subgroups are nontrivial.

Definition 53 (Injective)   A mapping is called injective if there is at most one value for each element . This means that every preimage in has an image in but there may be elements in which are not obtained as images.

Definition 54 (Surjective)   A mapping is called surjective if has at least one solution for every . Several identical images in may have different preimages in .

Definition 55 (Bijective)   A mapping that is both injective and surjective is called bijective. It maps every preimage from to a distinct image in . There are no elements in that cannot be obtained as images.

Definition 56 (Vector Space)   A vector space over a field is a set associated with two binary operations. The elements of are called vectors, while the elements of are called scalars. The binary operations are addition

 (11.3)

which is commutative as well as associative and which possesses a neutral as well as an inverse element, and scalar multiplication

 (11.4)

which is distributive with addition. is closed under its two binary operations.

Definition 57 (Linear Mapping)   A mapping is called linear, if the following relation holds

 (11.5)

A mapping

 (11.6)

that is linear in both of its arguments, as in the following relations

 (11.7) (11.8)

is called bilinear.

The extension of this notion to more than two arguments is called a multi-linear mapping.

Definition 58 (Homomorphism)   A map of a group into a group is a homomorphism if . For any groups and , there is always at least one homomorphism , namely the trivial homomorphism defined by , where is the identity element in .

Definition 59 (Kernel)   Let be a homomorphism. The subgroup , consisting of all elements of mapped by into the identity of , is the kernel of , denoted by .

Next: 12. STL Iterator Analysis Up: 4 Applied Concepts Previous: 10. Summary and Outlook

R. Heinzl: Concepts for Scientific Computing