7. Finite Graph Algorithms

The word vertices is the plural of the noun vertex.

An equivalence relation on a non-empty set \(S\) is a set, say \(R\), of ordered pairs of elements of \(S\), with the following properties for \(R\):If \(R\) is an equivalence relation on a non-empty set \(S\), then the set of all equivalence classes of the elements of \(S\) forms a partition of \(S\) into disjoint non-empty subsets of \(S\).

The proof follows fairly quickly from assertions (d),(e), and (f) above.

“Iso-”, same; “morph”, form.

(DIKE-struh) In case you haven’t heard of him before, he became an object of heated controversy because of a letter he wrote in 1968 to the Communications of the ACM. The letter was printed under the title “Go To Statement Considered Harmful”. A goto instruction in a programming language is an instruction that allows execution to be directed from any place in a program to any other specified place (the place is specified by a label). In assembly languages the JUMP and BRANCH instructions are goto instructions. In languages such as old FORTRAN and old BASIC, the GOTO is indispensable for control-flow. Dijkstra argued that availability of a goto instruction in high level languages was bad because it encouraged promiscuous transfers of execution that made programs hard to read and debug. He and several colleagues proved that in languages that include the now familiar control-flow instructions such as “if... else....” and “while”, no goto statement is logically necessary. Dijkstra’s letter generated a storm of letters arguing for and against the proposal he had made. Today most high level languages still have the goto instruction available, but programmers are strongly discouraged from ever using this instruction, since it creates “unstructured” code.