:: wikimiki.org ::

Diameter

Diameter

For the authentication, authorisation, and accounting protocol, see DIAMETER. In geometry, a diameter (Greek words diairo = divide and metro = measure) of a circle is any straight line segment that passes through the center and whose endpoints are on the circular boundary, or, in more modern usage, the length of such a line segment. When using the word in the more modern sense, one speaks of the diameter rather than a diameter, because all diameters of a circle have the same length. This length is twice the radius. The diameter of a circle is also the longest chord that the circle has. The diameter of a connected graph is the distance between the two vertices which are furthest from each other. The distance between two vertices a and b is the length of the shortest path connecting them (for the length of a path, see Graph theory). The two definitions given above are special cases of a more general definition. The diameter of a subset of a metric space is the least upper bound of the distances between pairs of points in the subset. So, if A is the subset, the diameter is :sup .

Diameter symbol

least upper bound The symbol or variable for diameter is similar in size and design to ø, the lowercase letter o with stroke. Unicode provides character number 8960 (hexadecimal 2300) for the symbol, which can be encoded in HTML webpages as ⌀ or ⌀. Proper display of this character, however, is unlikely in most situations, as most fonts do not have it included. (Your browser displays ⌀ and ⌀ in the current font.) In most situations the letter ø is acceptable, obtained in Microsoft Windows by holding the [Alt] key down while entering 0 2 4 8 on the numeric keypad. It is important not to confuse a diameter symbol (ø) with the empty set symbol, similar to the uppercase Ø. Diameter is also sometimes called phi (pronounced the same as "fie"), although this seems to come from the fact that Ø and ø look like Φ and φ, the letter phi in the Greek alphabet. See also: angular diameter, hydraulic diameter Category:Elementary geometry Category:Length ja:径

Diameter

Diameter symbol

Geometry

Geometry (Greek γεωμετρία; geo = earth, metria = measure) arose as the field of knowledge dealing with spatial relationships. It was one of the two fields of pre-modern mathematics, the other being the study of numbers. In modern times, geometric concepts have been generalized to a high level of abstraction and complexity, and have been subjected to the methods of calculus and abstract algebra, so that many modern branches of the field are barely recognizable as the descendants of early geometry. (See areas of mathematics and algebraic geometry.)

The earliest geometry

The earliest recorded beginnings of geometry may be traced to Ancient Egypt (see geometry in Egypt) and Ancient Babylon (see Babylonian mathematics) around 3000 B.C. Early geometry was a collection of empirically discovered principles concerning lengths, angles, areas, and volumes, which were developed to meet some practical need in surveying, construction, astronomy, and various crafts. Among these were some surprisingly sophisticated principles, and a modern mathematician might be hard put to derive some of them without the use of calculus. For example, both the Egyptians and the Babylonians were aware of versions of the Pythagorean theorem about 1500 years before Pythagoras; the Egyptians had a correct formula for the volume of a frustum of a square pyramid; the Babylonians had a trigonometry table. Chinese culture at this same time period was equally advanced, so it is likely that they had an equally advanced mathematics, but no artifacts have survived from which we could learn about it. This may be partly due to their early use of paper, rather than clay tablets or stone, to record their achievements.

The Greek period (c. 600 B.C. – 600 A.D.)

The Greek Period must be considered in detail, since geometry, for most of its history, was what the Greeks made it. For the Ancient Greeks, geometry was the crown jewel of their sciences, reaching a completeness and perfection of methodology that no other branch of their knowledge had attained. They expanded the range of geometry to many new kinds of figures, curves, surfaces, and solids; they changed its methodology from trial-and-error to logical deduction; they recognized that geometry studies “eternal forms”, or abstractions, of which physical objects are only approximations; and they developed the idea of an “axiomatic theory”, which, for more than 2000 years, was regarded to be the ideal paradigm for all scientific theories.

Thales and Pythagoras

Thales (635-543 B.C.) of Ionia (now southwestern Turkey), was the first to whom deduction in mathematics is attributed. There are five geometric propositions for which he wrote deductive proofs, though his proofs have not survived. Pythagoras (582-496 B.C.) of Ionia, and later, Italy, then colonized by Greeks, may have been a student of Thales, and probably traveled to Babylon and Egypt. The theorem that bears his name was not his discovery, but he was the first to give a deductive proof of it. He gathered a group of students around him to study mathematics, music, and philosophy, and together they discovered most of what high school students learn today in their geometry courses. In addition, they made the profound discovery of incommensurable lengths and irrational numbers.

Plato

Plato (427-347 B.C.), the philosopher most esteemed by the Greeks, had inscribed above the entrance to his famous school, “Let none enter here who are ignorant of geometry.” Though he was not a mathematician himself, his views on mathematics had great influence. Mathematicians thus accepted his belief that geometry should use no tools but a compass and straight edge – never measuring instruments such as a marked ruler or a protractor, because these were a workman’s tools, not worthy of a scholar. This dictum led to a deep study of the possible ruler and compass constructions, and three classic ruler-and-compass problems: how to use these tools to trisect an angle, to construct a cube twice the volume of a given cube, and to construct a square equal in area to a given circle. The proofs of the impossibility of these constructions, finally achieved in the 19th century, led to important principles regarding the deep structure of the real number system. Aristotle (384-322 B.C.), Plato’s greatest pupil, wrote a treatise on methods of reasoning used in deductive proofs (see Logic) which was not substantially improved upon until the 19th century.

Euclid

Euclid (365?-275? B.C.), probably a student of one of Plato’s students, wrote a treatise in 13 books (chapters), titled The Elements of Geometry, in which he presented geometry in the ideal axiomatic form. The treatise is not a compendium of all that the Greeks knew at the time about geometry; Euclid himself wrote eight more advanced books on geometry. We know from other references that Euclid’s was not the first elementary geometry textbook, but it was so much superior that the others fell into disuse and were lost. He was brought to the university at Alexandria by Ptolemy I, King of Egypt. The Elements began with definitions of terms, fundamental geometric principles (called axioms or postulates), and general quantitative principles (called common notions) from which all the rest of geometry could be logically deduced. Following are his five axioms, somewhat paraphrased to make the English easier to read. # Any two points can be joined by a straight line. # Any finite straight line can be extended in a straight line. # A circle can be drawn with any center and any radius. # All right angles are equal to each other. # If two straight lines in a plane are crossed by another straight line (called the transversal), and the interior angles between the two lines and the transversal lying on one side of the transversal add up to less than two right angles, then on that side of the transversal, the two lines extended will intersect (also called the parallel postulate). It was soon observed, and no doubt Euclid himself knew, that his fifth axiom could be replaced by the shorter statement “Given a line and a point not on the line, there is only one line through the given point and in the same plane with the given line that does not intersect the given line.” This is called Playfair’s Axiom, after the British teacher who proposed to make the replacement in all the school textbooks. The axioms, according to Plato, should be simple and self-evident principles, so clearly true that they need no proof. Euclid’s first four axioms meet this criterion, but the fifth, even if replaced by Playfair’s Axiom, is not simple, and most would say not self-evident like the first four. The fifth resembled more the theorems that Euclid proved from the axioms. Furthermore, Euclid developed a substantial part of his theory of triangles without using the Fifth Axiom. The speculation arose, probably during Euclid’s lifetime, that the Fifth Axiom can and should be proved as a theorem from the first four, and thus is unnecessary as an axiom. Thus began many centuries of attempts to prove the Fifth Axiom, and the question was not settled until the 19th century.

Archimedes

Archimedes (287-212 B.C.), of Syracuse, Sicily, when it was a Greek city-state, was the greatest of the Greek mathematicians, and often named as one of the three greatest of all time (along with Isaac Newton and Carl Friedrich Gauss). Had he not been a mathematician, he would still be remembered as a great physicist, engineer, and inventor. In his mathematics, he developed methods very similar to the coordinate systems of analytic geometry, and the limiting process of integral calculus. The only element lacking for the creation of these fields was an efficient algebraic notation in which to express his concepts.

After Archimedes

After Archimedes, Greek mathematics began to decline. There were a few minor stars yet to come, but the golden age of geometry was over. Proclus (410-485), author of Commentary on the First Book of Euclid, was one of the last important players in Greek geometry. He was a competent geometer, but more importantly, he was a superb commentator on the works that preceded him. Much of that work did not survive to modern times, and is known to us only through his commentary. The Roman Republic and Empire that succeeded and absorbed the Greek city-states produced excellent engineers, but no mathematicians of note.

The Middle Ages, Renaissance, and Reformation

The great library of Alexandria was burned. There is a growing consensus among historians that the Library of Alexandria likely suffered from several destructive events, but that the destruction of Alexandria's pagan temples in the late 4th century was probably the most severe and final one. The evidence for that destruction is the most definitive and secure. Caesar's invasion may well have led to the loss of some 40,000-70,000 scrolls in a warehouse adjacent to the port (as Luciano Canfora argues, they were likely copies produced by the Library intended for export), but it is unlikely to have affected the Library or Museum, given that there is ample evidence that both existed later. Civil wars, decreasing investments in maintenance and acquisition of new scrolls and generally declining interest in non-religious pursuits likely contributed to a reduction in the body of material available in the Library, especially in the fourth century. The Serapeum was certainly destroyed by Theophilus in 391, and the Museum and Library may have fallen victim to the same campaign. The Islamic ascendency in the Middle East, north Africa, and Spain began about 640 A.D. Original Arab mathematics during this period was primarily algebraic rather than geometric, though there were important commentaries on geometry. Omar Khayyám, for example, was a geometer as well as a poet. Scholarship in Europe declined until even the great works of antiquity were lost to them, and survived only in the Islamic centers of learning. When Europe started to emerge from the intellectual darkness of the Middle Ages, the writers of Ancient Greece and Rome were rediscovered in Islamic libraries and translated from Arabic into Latin. Euclid’s Elements of Geometry was recovered, and the rigorous deductive methods of geometry were relearned. Development of geometry in the style of Euclid resumed, resulting in an abundance of new theorems and concepts, many of them very profound and elegant.

The 17th and early 18th centuries

In the early 17th century, there were two important developments in geometry. The first and most important was the creation of analytic geometry, or geometry with coordinates and equations, by Rene Descartes (1596-1650) and Pierre de Fermat (1601-1665). This was a necessary precursor to the development of calculus and a precise quantitative science of physics. The second geometric development of this period was the systematic study of projective geometry by Girard Desargues (1591-1661). Projective geometry is the study of geometry without measurement, just the study of how points align with each other. There had been some early work in this area by Greek geometers, notably Pappus (c. 340). The greatest flowering of the field occurred with Jean-Victor Poncelet (1788-1867). In the late 17th century, calculus was developed independently and almost simultaneously by Isaac Newton (1642-1727) and Gottfried Wilhelm von Leibniz (1646-1716). This was the beginning of a new field of mathematics now called analysis. Though not itself a branch of geometry, it is applicable to geometry, and it solved two families of problems that had long been almost intractable: finding tangent lines to odd curves, and finding areas enclosed by those curves. The methods of calculus reduced these problems mostly to straightforward matters of computation.

The late 18th and 19th centuries

Non-Euclidean geometry

The old problem of proving Euclid’s Fifth Postulate, the "Parallel Postulate", from his first four postulates had never been forgotten. Beginning not long after Euclid, many attempted demonstrations were given, but all were later found to be faulty, through allowing into the reasoning some principle which itself had not been proved from the first four postulates. By 1700 a great deal had been discovered about what can be proved from the first four, and what the pitfalls were in attempting to prove the fifth. Saccheri, Lambert, and Legendre each did excellent work on the problem in the 18th century, but still fell short of success. In the early 19th century, Gauss, Johann Bolyai, and Lobatchewsky, each independently, took a different approach. Beginning to suspect that it was impossible to prove the Parallel Postulate, they set out to develop a self-consistent geometry in which that postulate was false. In this they were successful, thus creating the first non-Euclidean geometry. By 1854, Bernhard Riemann, a student of Gauss, had applied methods of calculus in a ground-breaking study of the intrinsic (self-contained) geometry of all smooth surfaces, and thereby found a different non-Euclidean geometry. This work of Riemann later became fundamental for Einstein's theory of relativity. It remained to prove mathematically that the non-Euclidean geometry was just as self-consistent as Euclidean geometry, and this was first accomplished by Beltrami in 1868. With this, non-Euclidean geometry was established on an equal mathematical footing with Euclidean geometry. While it was now known that different geometric theories were mathematically possible, the question remained, "Which one of these theories is correct for our physical space?" The mathematical work revealed that this question must be answered by physical experimentation, not mathematical reasoning, and uncovered the reason why the experimentation must involve immense (interstellar, not earth-bound) distances. With the development of relativity theory in physics, this question became vastly more complicated.

Introduction of mathematical rigor

All the work related to the Parallel Postulate revealed that it was quite difficult for a geometer to separate his logical reasoning from his intuitive understanding of physical space, and, moreover, revealed the critical importance of doing so. Careful examination had uncovered some logical inadequacies in Euclid's reasoning, and some unstated geometric principles to which Euclid sometimes appealed. This critique paralleled the crisis occurring in calculus and analysis regarding the meaning of infinite processes such as convergence and continuity. In geometry, there was a clear need for a new set of axioms, which would be complete, and which in no way relied on pictures we draw or on our intuition of space. Such axioms were given by David Hilbert in 1894 in his dissertation Grundlagen der Geometrie (Foundations of Geometry). Some other complete sets of axioms had been given a few years earlier, but did not match Hilbert's in economy, elegance, and similarity to Euclid's axioms.

Analysis situs, or topology

In the mid-18th century, it became apparent that certain progressions of mathematical reasoning recurred when similar ideas were studied on the number line, in two dimensions, and in three dimensions. Thus the general concept of a metric space was created so that the reasoning could be done in more generality, and then applied to special cases. This method of studying calculus- and analysis-related concepts came to be known as analysis situs, and later as topology. The important topics in this field were properties of more general figures, such as connectedness and boundaries, rather than properties like straightness, and precise equality of length and angle measurements, which had been the focus of Euclidean and non-Euclidean geometry. Topology soon became a separate field of major importance, rather than a sub-field of geometry or analysis.

The 20th century

External links

- [http://www.cut-the-knot.org/WhatIs/WhatIsGeometry.shtml What Is Geometry?] at cut-the-knot
- [http://www.elvenkids.com/tools/geometria/Geometria.php Geometria] An online tool to compute lines, surfaces and volumes of the main plane and solid figures, through direct and indirect formulas.
- [http://www.geogebra.at/ Geogebra] A free dynamic geometry tool, useful for exploring geometry.
- [http://agutie.homestead.com Geometry Step by Step from the Land of the Incas] by Antonio Gutierrez.
- [http://www.cut-the-knot.org/geometry.shtml Geometry] at cut-the-knot
- [http://www.islamicarchitecture.org/art/islamic-geometry-and-floral-patterns.html Islamic Geometry]
- Stanford Encyclopedia of Philosophy:
- [http://plato.stanford.edu/entries/geometry-finitism/ Finitism in Geometry]
- [http://plato.stanford.edu/entries/geometry-19th/ Geometry in the 19th Century]
- [http://www.egwald.com/geometry/index.php Online Interactive Geometric Objects] by Elmer G. Wiens Category:Geometry ko:기하학 ja:幾何学 simple:Geometry zh-min-nan:Kí-hô-ha̍k

Circle

:This article is about the shape and mathematical concept of circle; for other meanings, see Circle (disambiguation). Circle (disambiguation) In Euclidean geometry, a circle is the set of all points at a fixed distance, called the radius, from a fixed point, called the centre (center). The points can only be those that are part of a conic section; within the set of a plane bisecting a cone. Circles are simple closed curves, dividing the plane into an interior and exterior. Sometimes the word circle is used to mean the interior, with the circle itself called the circumference(C). Usually however, the circumference means the length of the circle, and the interior of the circle is called a disk or disc. An arc is any continuous portion of a circle.

Mathematical definitions

In an x-y coordinate system, the circle with centre (a, b) and radius r is the set of all points (x, y) such that :

\left( x - a \right)^2 + \left( y - b \right)^2=r^2.

If the circle is centered at the origin (0, 0), then this formula can be simplified to :

x^2 + y^2 = r^2.

The circle centered at the origin with radius 1 is called the unit circle. Expressed in parametric equations, (x, y) can be written as :x = a + r cos(t) :y = b + r sin(t). The slope a circle at a point (x, y) can be expressed with the following formula, assuming the center is at the origin and (x, y) is on the circle: :

y' = - \frac.

In the complex plane, a circle with a center at c and radius r has the equation

|z-c|^2 = r^2

. Since

|z-c|^2 = z\overline-\overlinez-c\overline+c\overline

, the slightly generalized equation

pz\overline + gz + \overline = q

for real p, q and complex g is sometimes called a generalized circle. It is important to note that not all generalized circles are actually circles. All circles are similar; as a consequence, a circle's circumference and radius are proportional, as are its area and the square of its radius. The constants of proportionality are 2π and π, respectively. In other words:
- Length of a circle's circumference =

2\pi \times r.

- Area of a circle =

\pi \times r^2.

The formula for the area of a circle can be derived from the formula for the circumference and the formula for the area of a triangle, as follows. Imagine a regular hexagon (six-sided figure) divided into equal triangles, with their apices at the center of the hexagon. The area of the hexagon may be found by the formula for triangle area by adding up the lengths of all the triangle bases (on the exterior of the hexagon), multiplying by the height of the triangles (distance from the middle of the base to the center) and dividing by two. This is an approximation of the area of a circle. Then imagine the same exercise with an octagon (eight-sided figure), and the approximation is a little closer to the area of a circle. As a regular polygon with more and more sides is divided into triangles and the area calculated from this, the area becomes closer and closer to the area of a circle. In the limit, the sum of the bases approaches the circumference 2πr, and the triangles' height approaches the radius r. Multiplying the circumference and radius and dividing by 2, we get the area, π r².

Properties

limit limit

Chord properties

- Chords equidistant from the centre of a circle are equal.
- Equal chords are equidistant from the centre.
- A line from the centre, perpendicular to a chord, bisects the chord.
- The line segment drawn from the centre to the midpoint of the chord is perpendicular to the chord.
- The perpendicular bisector of a chord passes through the centre of a circle.

Tangent properties

- The line drawn perpendicular to the end point of a radius is a tangent to the circle.
- A line drawn perpendicular to a tangent at the point of contact with a circle passes through the centre of the circle.
- Tangents drawn from a point outside the circle are equal in length.
- Two tangents can always be drawn from a point outside of the circle.

Inscribed angle theorem

- If a central angle and an inscribed angle of a circle are subtended by the same chord and on the same side of the chord, then the central angle is twice the inscribed angle.
- If two angles are inscribed on the same chord and on the same side of the chord , then they are equal.
- An inscribed angle subtended by a semicircle is a right angle.
- For a cyclic quadrilateral, the exterior angle is equal to the interior opposite angle.

Secant, tangent, and chord properties

- The chord theorem states that if two chords, CD and EF, intersect at G, then

CG \times DG = EG \times FG

. (Chord Theorem)
- If a tangent from an external point D meets the circle at C and a secant from the external point D meets the circle at G and E respectively, then

DC^2 = DG \times DE

. (Tangent Secant Theorem)
- If two secants, DG and DE, also cut the circle at H and F respectively, then

DH \times DG = DF \times DE

. (Corollary of the Tangent Secant Theorem)
- The angle between a tangent and chord is equal to the subtended angle on the opposite side of the chord. (Tangent Chord Property)
- If the angle subtended by the chord at the centre is 90 degrees then l = sqrt(2)
- r, where l is the length of the chord and r is the radius of the circle.

External links

- [http://agutie.homestead.com/files/clifford1.htm Clifford's Circle Chain Theorems.] This is a step by step presentation of the first theorem. Clifford discovered, in the ordinary Euclidean plane, a "sequence or chain of theorems" of increasing complexity, each building on the last in a natural progression. by Antonio Gutierrez from "Geometry Step by Step from the Land of the Incas"
- [http://www.cut-the-knot.org/pythagoras/Munching/circle.shtml Munching on Circles] at cut-the-knot Category:Conic sections ja:円 (数学) simple:Circle

Length

:This article is about the concept and measurement of distance. For usage in cricket, see line and length. In general English usage, length (symbols: l, L) is but one particular instance of distance – an object's length is how long the object is – but in the physical sciences and engineering, the word length is in some contexts used synonymously with "distance". Height is vertical distance; width (or breadth) is a lateral distance; an object's width is less than its length. No one speaks of "the length from here to Alpha Centauri", but rather of "the distance from here to Alpha Centauri," but when one speaks of distance more abstractly, one says "A kilometre or a mile, is a unit of length" or "...of distance", and the two statements are synonymous. Likewise, a mountain might be a mile in height. Length is the metric of one dimension of space. The metric of space itself is volume, or (length)³. Length is commonly considered to be one of the fundamental units, meaning that it cannot be defined in terms of other dimensions. However, a set of units can be constructed where units of length can be derived from fundamental physical constants - see Planck units and Planck length. Colloquially length sometimes refers to duration, especially when used in context of music.

Units of length(SI)

The SI unit of Length is the metre (U.S. spelling: meter), from which can be derived:from the regular basis of the foundation of the whole world
- centimetre
- kilometre

Other units of length

The Imperial and US customary units of length

- inch
- foot
- yard
- mile

Units are used in astronomy

- Astronomical unit
- Light year
- Parsec

External links

- [http://www.unitconversion.org/unit_converter/length.html Length Converter: convert between units of length, such as meter, yard, mile, and so on]
- [http://www.unitconversion.org/unit_converter/length-v.html Length Conversion table: convert selected unit to all other units of length]
- [http://calc.skyrocket.de/en/ Online Unit Converter - Conversion of many different units]
- Category:Norm ko:길이 ja:長さ

RADIUS

RADIUS (Remote Authentication Dial In User Service) is an AAA (authentication, authorization and accounting) protocol for applications such as network access or IP mobility. It is intended to work in both local and roaming situations. When you connect to an ISP using a modem, DSL, cable or wireless connection, you must enter your username and password. This information is passed to a Network Access Server (NAS) device over the Point-to-Point Protocol (PPP), then to a RADIUS server over the RADIUS protocol. The RADIUS server checks that the information is correct using authentication schemes like PAP, CHAP or EAP. If accepted, the server will then authorize access to the ISP system and select an IP address, L2TP parameters, etc. The RADIUS server will also be notified when the session starts and stops, so that the user can be billed accordingly; or the data can be used for statistical purposes. RADIUS was originally developed by Livingston Enterprises for their PortMaster series of Network Access Servers, but later (1997) published as RFC 2058 and RFC 2059 (current versions are RFC 2865 and RFC 2866). Now, several commercial and open-source RADIUS servers exist. Features can vary, but most can look up the users in text files, LDAP servers, various databases, etc. Accounting tickets can be written to text files, various databases, forwarded to external servers, etc. SNMP is often used for remote monitoring. RADIUS proxy servers are used for centralized administration and can rewrite RADIUS packets on the fly (for security reasons, or to convert between vendor dialects). RADIUS is extensible; most vendors of RADIUS hardware and software implement their own dialects. The DIAMETER protocol is the planned replacement for RADIUS, but is still backwards compatible.

Standards

The RADIUS protocol is currently defined in:
- RFC 2865 Remote Authentication Dial In User Service (RADIUS)
- RFC 2866 RADIUS Accounting Other relevant RFCs are:
- RFC 2548 Microsoft Vendor-specific RADIUS Attributes
- RFC 2607 Proxy Chaining and Policy Implementation in Roaming
- RFC 2618 RADIUS Authentication Client MIB
- RFC 2619 RADIUS Authentication Server MIB
- RFC 2620 RADIUS Accounting Client MIB
- RFC 2621 RADIUS Accounting Server MIB
- RFC 2809 Implementation of L2TP Compulsory Tunneling via RADIUS
- RFC 2867 RADIUS Accounting Modifications for Tunnel Protocol Support
- RFC 2868 RADIUS Attributes for Tunnel Protocol Support
- RFC 2869 RADIUS Extensions
- RFC 2882 Network Access Servers Requirements: Extended RADIUS Practices
- RFC 3162 RADIUS and IPv6
- RFC 3576 Dynamic Authorization Extensions to RADIUS

External links

- [http://www.untruth.org/~josh/security/radius/radius-auth.html An Analysis of the RADIUS Authentication Protocol]
- [http://www.freeradius.org/rfc/attributes.html List of RADIUS attributes] Category:Authentication methods Category:Internet protocols Category:Internet standards ja:RADIUS

Connected graph

In mathematics and computer science the connectivity of graphs is one of the basic concepts of graph theory. It is closely related to the concept of path. In network theory we are often interested how many connections (edges) in the network are allowed to fail before two nodes (vertices) become disconnected. Menger's theorem and Fulkerson's theorem provide characterizations of this problem. By adding weights to the edges of the graph we are able to consider network flow problems which allow a finer discussion of connectivity. Checking if a graph is connected, or even its number of connected components, is a very easy problem that can be solved in deterministic logarithmic space (see SL).

Connections

Given an undirected graph, two vertices u and v are called connected if there exists a path from u to v. Otherwise they are called disconnected. The graph is called connected graph if every pair of vertices in the graph is connected.

Cuts

A vertex cut for two vertices u and v is a set of vertices whose removal from the graph disconnects u and v. A vertex cut for the whole graph is a set of vertices whose removal renders the graph disconnected. The vertex connectivity κ(G) for a graph G is the size of minimum vertex cut. A graph is called k-vertex-connected if its vertex connectivity is k or greater. The same concept can be defined for edges. An edge cut for two vertices u and v is a set of edges whose removal from the graph disconnects u and v. A edge cut for the whole graph is a set of edges whose removal renders the graph disconnected. The edge connectivity κ'(G) for a graph G is the size of the minimum edge cut. A graph is called k-edge-connected if its edge connectivity is k or greater.

Examples

- The vertex and edge connectivities of a disconnected graph are both 0
- A connected graph is 1-connected by definition
- A complete graph is maximally connected; if it has n vertices, its edge connectivity is n
- A tree is minimally connected; its edge connectivity is 1

Properties

- Connectedness is preserved by graph homomorphisms.
- If G is connected then the line graph L(G) is connected too.
- A graph is k-vertex-connected if and only if it contains k vertex independent paths between any two vertices.
- A graph is k-edge-connected if and only if it contains k edge independent paths between any two edges.
- Given a k-vertex-connected graph G then for every set of vertices U there exists a cycle in G containing U
- Given a connected graph the distance between two vertices u and v is equal to the number of pairwise disjunct edge cut sets which separate u and v.

Vertex

In geometry, a vertex (Latin: whirl, whirlpool; plural vertices) is a corner of a polygon (where two sides meet) or of a polyhedron (where three or more faces and an equal number of edges meet). In graph theory, a graph describes a set of connections between objects. Each object is called a node or vertex. The connections themselves are called edges or arcs. In 3D computer graphics, a vertex is a point in 3D space with a particular location, usually given in terms of its x, y, and z coordinates. It is one of the fundamental structures in polygonal modelling: two vertices, taken together, can be used to define the endpoints of a line; three vertices can be used to define a planar triangle. Vertices are commonly confused with vectors because a vertex can be described as a vector from a coordinate system's origin. They are, however, two completely different things. In anatomy, the vertex is the highest point of the skull in the anatomical position (i.e. standing upright). It lies between the parietal bones in the median sagittal plane. In Astrology, the Vertex is a point in 3D space, seen near the Eastern horizon and the Ascendant in the (two-dimensional) starchart. Planets close to it lend their personality to the event(s) the chart captures.

Graph theory

In mathematics and computer science, graph theory studies the properties of graphs. Informally, a graph is a set of objects called vertices (or nodes) connected by links called edges (or arcs) which can be directed (assigned a direction). Typically, a graph is designed as a set of dots (the vertices) connected by lines (the edges). Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be represented by graphs. The link structure of a website could be represented by a directed graph: the vertices are the web pages available at the website and there's a directed edge from page A to page B if and only if A contains a link to B. The development of algorithms to handle graphs is therefore of major interest in computer science. A graph structure can be extended by assigning a weight to each edge. Graphs with weights can be used to represent many different concepts; for example if the graph represents a road network, the weights could represent the length of each road¹. Another way to extend basic graphs is by making the edges to the graph directional (A links to B, but B does not necessarily link to A, as in webpages), technically called a directed graph or digraph. A digraph with weighted edges is called a network. Networks have many uses in the practical side of graph theory, network analysis (for example, to model and analyze traffic networks or to discover the shape of the internet -- see Applications below). However, it should be noted that within network analysis, the definition of the term "network" may differ, and may often refer to a simple graph.

History

One of the first results in graph theory appeared in Leonhard Euler's paper on Seven Bridges of Königsberg, published in 1736. It is also regarded as one of the first topological results in geometry; that is, it does not depend on any measurements. This illustrates the deep connection between graph theory and topology. In 1845 Gustav Kirchhoff published his Kirchhoff's circuit laws for calculating the voltage and current in electric circuits. In 1852 Francis Guthrie posed the four color problem which asks if it is possible to color, using only four colors, any map of countries in such a way as to prevent two bordering countries from having the same color. This problem, which was only solved a century later in 1976 by Kenneth Appel and Wolfgang Haken, can be considered the birth of graph theory. While trying to solve it mathematicians invented many fundamental graph theoretic terms and concepts.

Definition

Drawing graphs

Graphs are represented graphically by drawing a dot for every vertex, and drawing an arc between two vertices if they are connected by an edge. If the graph is directed the direction is indicated by drawing an arrow. A graph drawing should not be confused with the graph itself (the abstract, non-graphical structure) as there are several ways to structure the graph drawing. All that matters is which vertices are connected to which others by how many edges and not the exact layout. In practise it is often difficult to decide if two drawings represent the same graph. Depending on the problem domain some layouts may be better suited and easier to understand than others.

Graphs as data structures

There are different ways to store graphs in a computer system. The data structure used depends on both the graph structure and the algorithm used for manipulating the graph. Theoretically one can distinguish between list and matrix structures but in concrete applications the best structure is often a combination of both. List structures are often preferred for sparse graphs as they have smaller memory requirements. Matrix structures on the other hand provide faster access but can consume huge amounts of memory if the graph is very large.

List structures

- Incidence list - The edges are represented by an array containing pairs (ordered if directed) of vertices (that the edge connects) and eventually weight and other data.
- Adjacency list - Much like the incidence list, each node has a list of which nodes it is adjacent to. This can sometimes result in "overkill" in an undirected graph as node 3 may be in the list for node 2, then node 2 must be in the list for node 3. Either the programmer may choose to use the unneeded space anyway, or he/she may choose to list the adjacency once. This representation is easier to find all the nodes which are connected to a single node, since these are explicitly listed.

Matrix structures

- Incidence matrix - The graph is represented by a matrix of E (edges) by V (vertices), where [edge, vertex] contains the edge's data (simplest case: 1 - connected, 0 - not connected).
- Adjacency matrix - there is an N by N matrix, where N is the number of vertices in the graph. If there is an edge from some vertex x to some vertex y, then the element

M_

is 1, otherwise it is 0. This makes it easier to find subgraphs, and to reverse graphs if needed.
- Admittance matrix or Kirchhoff matrix or Laplacian matrix - is defined as degree matrix minus adjacency matrix and thus contains adjacency information and degree information about the vertices

Graph problems

Finding subgraphs

A common problem, called subgraph isomorphism problem, is finding subgraphs in a given graph. Many graph properties are hereditary, which means if a certain subgraph has a property so does the whole graph. For example a graph is non planar if it contains the complete bipartite graph

K_

(See Three cottage problem) or if it contains the complete graph

K_

. Unfortunately, finding maximal subgraphs of a certain kind is often an NP-complete problem.
- finding the largest complete graph is called the clique problem (NP-complete)
- finding the largest independent set is called the independent set problem (NP-complete)

Covering Problems

Covering problems are specific instances of subgraph finding problems, and tend to be closely related to the clique problem or independent set problem.
- Set cover problem
- Vertex cover problem

Important algorithms

- Bellman-Ford algorithm
- Dijkstra's algorithm
- Ford-Fulkerson algorithm
- Kruskal's algorithm
- Nearest neighbour algorithm
- Prim's algorithm

Related areas of mathematics

- Ramsey theory
- Combinatorics

Applications

Many applications of graph theory exist in the form of network analysis. These split broadly into two categories. Firstly, analysis to determine structural properties of a network, such as whether or not it is a scale-free network, or a small-world network. Secondly, analysis to find a measurable quantity within the network, for example, for a transportation network, the level of vehicular flow within any portion of it. Graph theory is also used to study molecules in science. In condensed matter physics, the three dimensional structure of complicated simulated atomic structures can be studied quantitatively by gathering statistics on graph-theoretic properties related to the topology of the atoms. For example, Franzblau's shortest-path (SP) rings.

Subareas

Graph theory is diverse and contains many identifiable subareas. Some of them are:
- Algebraic graph theory
- Topological graph theory
- Geometric graph theory
- Extremal graph theory
- Metric graph theory
- Probabilistic graph theory

Prominent graph theorists

- Paul Erdős
- Frank Harary
- Denes König
- W.T. Tutte
- [http://www1.cs.columbia.edu/~sanders/graphtheory/people/alphabetic.html Graph theory white pages] for more graph theorists and their publications.

Notes

# The only information a weighted graph provides as such is (a) the vertices, (b) the edges and (c) the weights. Therefore the example in which the weights represent the roads' lengths doesn't imply that the weights are only present as informational bits of data: there is no actual topographical information associated with the graph, so unlike reading a map, measuring the distances between the vertices is completely meaningless -- without the weights, there would be no way of telling what the distance between the vertices is in real life.

External links

- [http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ Graph Theory online textbook]
- [http://www.utm.edu/departments/math/graph/ Graph theory tutorial]
- [http://www.cs.wpi.edu/~dobrush/cs507/presentation/2001/Project10/ppframe.htm Graph theory algorithm presentation]
- [http://students.ceid.upatras.gr/~papagel/project/contents.htm Some graph theory algorithm animations]
- Step through the algorithm to understand it.
- [http://www2.hig.no/~algmet/animate.html The compendium of algorithm visualisation sites]
- [http://www.nlsde.buaa.edu.cn/~kexu/benchmarks/graph-benchmarks.htm Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring]
- [http://www.nd.edu/~networks/gallery.htm Image gallery no.1: Some real-life networks]
- [http://www.aisee.com/graphs/ Image gallery no.2: More real-life graphs]
- [http://people.freenet.de/Emden-Weinert/graphs.html Graph links collection]
- [http://ttt.upv.es/~arodrigu/grafos/index.htm Grafos spanish copyleft software]
- [http://www.ffconsultancy.com/products/ocaml_for_scientists/complete/ Source code for computing neighbor shells in particle systems under periodic boundary conditions]
- [http://www1.cs.columbia.edu/~sanders/graphtheory/writings/journals.html Graph Theory Journals]
- [http://www1.cs.columbia.edu/~sanders/graphtheory/writings/books.html Graph Theory Books] Category:Discrete mathematics Category:Graph theory Category:Algebraic graph theory Category:Topological graph theory ko:그래프 이론 ja:グラフ理論 simple:Graph theory th:ทฤษฎีกราฟ

Metric space

In mathematics, a metric space is a set where a notion of distance between elements of the set is defined. The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space. The Euclidean metric of this space defines the distance between two points as the length of the straight line connecting them. The geometry of the space depends on the metric chosen, and by using a different metric we can construct interesting non-Euclidean geometries such as those used in the theory of general relativity. A metric space induces topological properties like open and closed sets which leads to the study of even more abstract topological spaces.

History

Maurice Fréchet introduced metric spaces in his work Sur quelques points du calcul fonctionnel, Rendic. Circ. Mat. Palermo 22(1906) 1-74.

Definition

A metric space is a 2-tuple (X,d) where X is a set and d is a metric on X, that is, a function :d : X × X → R such that # d(x, y) ≥ 0 (non-negativity) # d(x, y) = 0 if and only if x = y (identity of indiscernibles) # d(x, y) = d(y, x) (symmetry) # d(x, z) ≤ d(x, y) + d(y, z) (triangle inequality). The function d is also called distance function or simply distance. We often omit d and just write X for a metric space if it is clear from the context what metric we are using.

Examples

- The real numbers with the distance function d(x, y) = |y − x| given by the absolute value, and more generally Euclidean n-space with the Euclidean distance, are complete metric spaces.
- Hyperbolic plane.
- Any normed vector space is a metric space by defining d(x, y) = ||y − x||, see also distances based on norms. (If such a space is complete, we call it a Banach space). Example:
- the Manhattan norm gives rise to the Manhattan distance, where the distance between any two points, or vectors, is the sum of the distances between corresponding coordinates.
- The discrete metric, where d(x,y)=1 for all x not equal to y and d(x,y)=0 otherwise, is a simple but important example, and can be applied to all sets.
- The British Rail metric (also called the Post Office metric) on a normed vector space, given by d(x, y)=||x|| + ||y|| for distinct points x and y, and d(x, x) = 0. The name alludes to the tendency of railway journeys (or letters) to proceed via London, which is identified with the origin.
- The Chessboard distance, the number of moves a chess king would take to travel from x to y.
- If X is some set and M is a metric space, then the set of all bounded functions f : X → M (i.e. those functions whose image is a bounded subset of M) can be turned into a metric space by defining d(f, g) = sup_{x in X} d(f(x), g(x)) for any bounded functions f and g. If M is complete, then this space is complete as well.
- The Levenshtein distance, also called character edit distance, is a measure of the similarity between two strings u and v. The distance is the minimal number of deletions, insertions, or substitutions required to transform u into v.
- If X is a topological (or metric) space and M is a metric space, then the set of all bounded continuous functions from X to M forms a metric space if we define the metric as above: d(f, g) = sup_{x in X} d(f(x), g(x)) for any bounded continuous functions f and g. If M is complete, then this space is complete as well.
- If M is a connected Riemannian manifold, then we can turn M into a metric space by defining the distance of two points as the infimum of the lengths of the paths (continuously differentiable curves) connecting them.
- If G is an undirected connected graph, then the set V of vertices of G can be turned into a metric space by defining d(x, y) to be the length of the shortest path connecting the vertices x and y.
- Similarly (apart from mathematical details):
- For any system of roads and terrains the distance between two locations can be defined as the length of the shortest route. To be a metric there should not be one-way roads. Examples include some mentioned above: the Manhattan norm, the British Rail metric, and the Chessboard distance.
- More generally, for any system of roads and terrains, with given maximum possible speed at any location, the "distance" between two locations can be defined as the time the fastest route takes. To be a metric there should not be one-way roads, and the maximum speed should not depend on direction.
- Similarly, in 3D, the metrics on the surface of a polyhedron include the ordinary metric, and the distance over the surface; a third metric on the edges of a polyhedron is one where the "paths" are the edges. For example, the distance between opposite vertices of a unit cube is √3, √5, and 3, respectively.
- If M is a metric space, we can turn the set K(M) of all compact subsets of M into a metric space by defining the Hausdorff distance d(X, Y) = inf. In this metric, two elements are close to each other if every element of one set is close to some element of the other set. One can show that K(M) is complete if M is complete.
- The set of all (isometry classes of) compact metric spaces form a metric space with respect to Gromov-Hausdorff distance.

Metric spaces as topological spaces

In any metric space M we can define the open balls as the sets of the form ::B(x; r) = , where x is in M and r is a positive real number, called the radius of the ball. A subset of M which is a union of (finitely or infinitely many) open balls is called an open set. The complement of an open set is called closed. Every metric space is automatically a topological space, the topology being the set of all open sets. A topological space which can arise in this way from a metric space is called a metrizable space; see the article on metrization theorems for further details. Since metric spaces are topological spaces, one has a notion of continuous function between metric spaces. Without referring to the topology, this notion can also be directly defined using limits of sequences; this is explained in the article on continuous functions.

Boundedness and compactness

A metric space M is called bounded if there exists some number r, such that d(x,y) ≤ r for all x and y in M. The smallest possible such r is called the diameter of M. The space M is called precompact or totally bounded if for every r > 0 there exist finitely many open balls of radius r whose union equals M. Since the set of the centres of these balls is finite, it has finite diameter, from which it follows (using the triangle inequality) that every totally bounded space is bounded. The converse does not hold, since any infinite set can be given the discrete metric (the first example above) under which it is bounded and yet not totally bounded. A useful characterisation of compactness for metric spaces is that a metric space is compact if and only if it is complete and totally bounded. Note that compactness depends only on the topology, while boundedness depends on the metric. Note that in the context of intervals in the space of real numbers and occasionally regions in a Euclidean space Rⁿ a bounded set is referred to as "a finite interval" or "finite region". However boundedness should not in general be confused with "finite", which refers to the number of elements, not to how far the set extends; finiteness implies boundedness, but not conversely. By restricting the metric, any subset of a metric space is a metric space itself (a subspace). We call such a subset complete, bounded, totally bounded or compact if it, considered as a metric space, has the corresponding property.

Separation properties and extension of continuous functions

Metric spaces are paracompact Hausdorff spaces and hence normal (indeed they are perfectly normal). An important consequence is that every metric space admits partitions of unity and that every continuous real-valued function defined on a closed subset of a metric space can be extended to a continuous map on the whole space (Tietze extension theorem). It is also true that every real-valued Lipschitz-continuous map defined on a subset of a metric space can be extended to a Lipschitz-continuous map on the whole space.

Distance between points and sets

A simple way to construct a function separating a point from a closed set (as required for a completely regular space) is to consider the distance between the point and the set. If (M,d) is a metric space, S is a subset of M and x is a point of M, we define the distance from x to S as :d(x,S) = inf Then d(x, S) = 0 if and only if x belongs to the closure of S. Furthermore, we have the following generalization of the triangle inequality: :d(x,S) ≤ d(x,y) + d(y,S) which in particular shows that the map x |-> d(x,S) is continuous.

Equivalence of metric spaces

Comparing two metric spaces one can distinguish various degrees of equivalence. To preserve at least the topological structure induced by the metric, these require at least the existence of a continuous function between them (morphism preserving the topology of the metric spaces). Given two metric spaces (M₁, d₁) and (M₂, d₂):
- They are called topologically isomorphic (or homeomorphic) if there exists a homeomorphism between them.
- They are called uniformly isomorphic if there exists a uniform isomorphism between them.
- They are called isometrically isomorphic if there exists a bijective isometry between them. In this case, the two spaces are essentially identical. An isometry is a function f : M₁ → M₂ which preserves distances: d₂(f(x), f(y)) = d₁(x, y) for all x, y in M₁. Isometries are necessarily injective.
- They are called similar if there exists a positive constant k > 0 and a bijective function f, called similarity such that f : M₁ → M₂ and d₂(f(x), f(y)) = k d₁(x, y) for all x, y in M₁.
- They are called similar (of the second type) if there exists a bijective function f, called similarity such that f : M₁ → M₂ and d₂(f(x), f(y)) = d₂(f(u), f(v)) if and only if d₁(x, y) = d₁(u, v) for all x, y,u, v in M₁. In case of Euclidean space with usual metric the two notions of similarity are equivalent.

Quotient metric space

If M is a metric space with metric d, and ~ is an equivalence relation on M, then we can endow the quotient set M/~ with the following (pseudo)metric. Given two equivalence classes [x] and [y], we define :

d'([x],[y]) = \inf\

where the infimum is taken over all finite sequences

(p_1, p_2, \dots, p_n)

and

(q_1, q_2, \dots, q_n)

with

[p_1]=[x]

[q_n]=[y]

[q_i]=[p_], i=1,2,\dots n-1

. In general this will only define a pseudometric, i.e.

d'([x],[y])=0

does not necessarily imply that [x]=[y]. However for nice equivalence relations (e.g., those given by gluing together polyhedra along faces), it is a metric. Moreover if M is a compact space, then the induced topology on M/~ is the quotient topology. The quotient metric d is characterized by the following universal property. If $f:(M,d)\longrightarrow(X,\delta)$ is a short map between metric spaces (that is, $\delta(f(x),f(y))\le d(x,y)$ for all x, y) satisfying f(x)=f(y) whenever $x\sim y,$ then the induced function $\overline:M/\sim\longrightarrow X$ , given by $\overline([x])=f(x)$ , is a short map $\overline:(M/\sim,d')\longrightarrow (X,\delta).$
See also

- Glossary of Riemannian and metric geometry
- topology
- triangle inequality
- Lipschitz continuity
- isometry, contraction mapping and short map
- Category of metric spaces
- Norm (mathematics)
References

- Dmitri Burago, Iu D Burago, Sergei Ivanov, A Course in Metric Geometry, American Mathematical Society, 2001, ISBN 0821821296.
External link

- [http://www.cut-the-knot.org/do_you_know/far_near.shtml Far and near — several examples of distance functions] at cut-the-knot
- [http://mathworld.wolfram.com/MetricSpace.html Metric Space] — Metric Spaces on Wolfram's MathWorld Category:Metric geometry Category:Topology ko:거리공간 ja:距離空間

Symbol

:For the Romanian choir, see Symbol (choir) A symbol, in its basic sense, is a conventional representation of a concept or quantity; i.e., an idea, object, concept, quality, etc. In more psychological and philosophical terms, all concepts are symbolic in nature, and representations for these concepts are simply token artifacts that are allegorical to (but do not directly codify) a symbolic meaning, or symbolism. Spoken language, for example, consists of distinct auditory tokens for representing symbolic concepts (words), arranged in an order which further suggests their meaning.

Nature of symbols

word]A symbol can be a material object whose shape or origin is related, by nature or convention, to the thing it represents: for instance, the cross is the main symbol of Christianity, and the scepter is a traditional symbol of royal power. A symbol can also be a more or less conventional image (i.e. an icon), or a detail of an image, or even a pattern or color: for example, the olive branch in heraldry represents peace, the halo is a conventional symbol of sainthood in Christian imagery, tartans are symbols of Scottish clans, and the color red is often used as a symbol for socialist movements, especially communism. More often, a symbol is a conventional written or printed sign (specifically, a glyph), usually standing for anything other than a sound (symbols for sounds are usually called graphemes, letters, logograms, diacritics, etc.). Thus mathematical symbols such as π and + represent quantities and operations, currency symbols represent monetary units, chemical symbols represent elements, and so forth. Symbols can also be immaterial entities like sounds, words and gestures. The ringing of gongs and bells, and the banging of a judge's gavel, often have conventional meanings in certain contexts; and bowing is a common way to indicate respect. In fact, every word in a natural language is a symbol for some concept or relationship between concepts. A symbol is usually recognized only within some specific culture, religion, or discipline, but a few hundred symbols are now recognized internationally. See list of common symbols and List of symbols.

Use of symbols

Human beings' ability to manipulate symbols allows them to explore the relationships between ideas, things, concepts, and qualities - far beyond the explorations of which any other species on earth is capable. The discipline of semiotics studies symbols and symbol systems in general; semantics is specifically concerned with the main meaning of words or other linguistic units. Literary works are often admired for their artful use of symbolism, i.e. the use of words, phrases and situations to evoke ideas and feelings beyond their plain interpretations; these uses are the subject of literary semiotics. Religious and metaphysical writings are also known for their use of esoteric symbolism. Alchemical writings made extensive use of symbols for spiritual and chemical processes (which they also saw as symbols of each other). The interpretation of dreams as symbols of one's experiences is a main feature of Freudian psychoanalysis and Jungian analytical psychology.

Etymology

The word "symbol" came to the English language, by way of Middle English, Old French, and Latin, from the Greek σύμβολον súmbolon from the root words σύμ- (sym-) meaning "together" and βολή bolḗ "a throw", having the approximate meaning of "to throw together", so "sign, ticket, or contract".

External links

- [http://www.symbols.com Symbol search engine]
- [http://altreligion.about.com/library/glossary/blsymbols.htm Religious and Cultural Symbols]
- ja:シンボル simple:Symbol

HTML

In computing, HyperText Markup Language (HTML) is a markup language designed for the creation of web pages and other information viewable in a browser. HTML is used to structure information — denoting certain text as headings, paragraphs, lists and so on — and can be used to describe, to some degree, the appearance and semantics of a document. Originally defined by Tim Berners-Lee and further developed by the IETF with a simplified SGML syntax, HTML is now an international standard (ISO/IEC 15445:2000). Later HTML specifications are maintained by the World Wide Web Consortium (W3C). Early versions of HTML were defined with looser syntactic rules which helped its adoption by those unfamiliar with web publishing. Web browsers commonly made assumptions about intent and proceeded with rendering of the page. Over time, the trend in the official standards has been to create an increasingly strict language syntax; however, browsers still continue to render pages that are far from valid HTML. XHTML, which applies the stricter rules of XML to HTML to make it easier to process and maintain, is the W3C's successor to HTML. As such, many consider XHTML to be the "current version" of HTML, but it is a separate, parallel standard; the W3C continues to recommend the use of either XHTML 1.1, XHTML 1.0, or HTML 4.01 for web publishing.

Introduction

HTML is a form of markup that is oriented toward the construction of single-page text documents with specialized rendering software called HTML user agents, the most common example of which is a web browser. HTML provides a means by which the document's content can be annotated with various kinds of metadata and rendering hints. The rendering cues may range from minor text decorations, such as specifying that a certain word be underlined or that an image be inserted, to sophisticated imagemaps and form definitions. The metadata may include information about the document's title and author, structural information such as headings, paragraphs, lists, and information that allows the document to be linked to other documents to form a hypertext web. HTML is a text based format that is designed to be both readable and editable by humans using a text editor. However, writing and updating a large number of pages by hand in this way is time consuming, requires a good knowledge of HTML and can make consistency difficult to maintain. Visual HTML editors such as Macromedia Dreamweaver, Adobe GoLive or Microsoft FrontPage allow the creation of web pages to be treated much like word processor documents. The code generated by these programs can be of poor quality. However, the open-source visual HTML editor Nvu generates code of high quality. HTML can be generated on the fly using a server-side scripting system such as Perl, PHP, JSP, or ASP. Many web applications like content management systems, wikis and web forums generate HTML pages.

Version history of the standard

- [http://www.w3.org/MarkUp/draft-ietf-iiir-html-01.txt Hypertext Markup Language (First Version)], published June 1993 as an Internet Engineering Task Force (IETF) working draft (not standard).
- [http://www.ietf.org/rfc/rfc1866.txt HTML 2.0], published November 1995 as IETF RFC 1866, and declared obsolete/historic by RFC 2854 in June 2000.
- [http://www.w3.org/TR/REC-html32 HTML 3.2], published January 14, 1997 as a W3C Recommendation.
- [http://www.w3.org/TR/REC-html40-971218/ HTML 4.0], published December 18, 1997 as a W3C Recommendation.
- [http://www.w3.org/TR/html401 HTML 4.01], published December 24, 1999 as a W3C Recommendation.
- [http://www.purl.org/NET/ISO+IEC.15445/15445.html ISO/IEC 15445:2000] ("ISO HTML", based on HTML 4.01 Strict), published May 15, 2000 as an ISO/IEC international standard.
- [http://www.w3.org/TR/xhtml1/ XHTML 1.0], published January 26, 2000 as a W3C Recommendation, later revised and republished August 1, 2002. There is no official standard HTML 1.0 specification because there were multiple informal HTML standards at the time. However, some people consider the initial edition provided by Tim Berners-Lee to be the definitive HTML 1.0. That version did not include an IMG element type. Work on a successor for HTML, then called "HTML+", began in late 1993, designed originally to be "A superset of HTML…which will allow a gradual rollover from the previous format of HTML". The first formal specification was therefore given the version number 2.0 in order to distinguish it from these unofficial "standards". Work on HTML+ continued, but it never became a standard. The HTML 3.0 standard was proposed by the newly formed W3C in March 1995, and provided many new capabilities such as support for tables, text flow around figures, and the display of complex math elements. Even though it was designed to be compatible with HTML 2.0, it was too complex at the time to be implemented, and when the draft expired in September 1995 work in this direction was discontinued due to lack of browser support. HTML 3.1 was never officially proposed, and the next standard proposal was HTML 3.2 (code-named "Wilbur"), which dropped the majority of the new features in HTML 3.0 and instead adopted many browser-specific element types and attributes which had been created for the Netscape and Mosaic web browsers. Math support as proposed by HTML 3.0 finally came about years later with a different standard, MathML. HTML 4.0 likewise adopted many browser-specific element types and attributes, but at the same time began to try to "clean up" the standard by marking some of them as deprecated, and suggesting they not be used. Minor editorial revisions to the HTML 4.0 specification were published as HTML 4.01. The most common extension for files containing HTML is .html, however, older operating systems, such as DOS, limit file extensions to three letters, so a .htm extension is also used. Although perhaps less common now, the shorter form is still widely supported by current software.

Markup element types

Below are the kinds of markup element types in HTML.
- Structural markup. Describes the purpose of text. For example, ::Golf :directs the browser to render "Golf" as a second-level heading, similar to "Markup element types" at the start of this section. Structural markup does not denote any specific rendering, but most web browsers have standardised on how elements should be formatted. For example, by default, headings like these will appear in large, bold text. Further styling should be done with Cascading Style Sheets (CSS).
- Presentational markup. Describes the appearance of the text, regardless of its function. For example, ::boldface :will render "boldface" in bold text. In the majority of cases, using presentational markup is inappropriate, and presentation should be controlled by using CSS. In the case of both bold and italic there are elements which usually have an equivalent visual rendering but are more semantic in nature, namely strong emphasis and emphasis respectively. It is easier to see how an aural user agent should interpret the latter two elements.
- Hypertext markup. Links parts of the document to other documents. For example, ::Wikipedia :will render the word [http://wikipedia.org Wikipedia] as a hyperlink to the specified URL.

The Document Type Definition

In order to specify which version of the HTML standard they conform to, all HTML documents should start with a Document Type Declaration (informally, a "DOCTYPE"), which makes reference to a Document Type Definition (DTD). For example: This declaration asserts that the document conforms to the Strict DTD of HTML 4.01, which is purely structural, leaving formatting to Cascading Style Sheets. In some cases, the presence or absence of an appropriate DTD may influence how a web browser will display the page. In addition to the Strict DTD, HTML 4.01 provides Transitional and Frameset DTDs. The Transitional DTD was intended to gradually phase in the changes made in the Strict DTD, while the Frameset DTD was intended for those documents which contained frames.

Separation of style and content

Efforts of the web development community have led to a new thinking in the way a web document should be written; XHTML epitomizes this effort. Standards stress using markup which suggests the structure of the document, like headings, paragraphs, block quoted text, and tables, instead of using markup which is written for visual purposes only, like <font>, <b> (bold), and <i> (italics). Some of these elements are not permitted in certain varieties of HTML, like HTML 4.01 Strict. CSS provides a way to separate the HTML structure from the content's presentation, by keeping all code dealing with presentation defined in a CSS file. See separation of style and content.

Serving HTML

The World Wide Web primarily uses HTTP to serve HTML documents to users. In order to do this correctly, it is necessary for the document to be described correctly: the necessary metadata includes the MIME Type (typically "text/html", although other choices include "application/xhtml+xml") and the character encoding (see Character encodings in HTML).

HTML Email

HTML is also used in email messages. Many email clients include a GUI HTML editor for composing emails and a rendering engine for displaying them once received. Use of HTML in email is quite controversial due to a variety of issues. The main benefit is the ability to decorate an email with presentational attributes (bold headings etc). However, there are a number of disadvantages, which include:
- the recipient may not have an email client that can display HTML
- the email has larger size because lots of formatting will be much larger than the plain text equivalent. This issue is made slightly worse by the fact that, for compatibility, most clients send a plaintext version as well.
- overuse of formatting (there was at one stage a craze for making letterheads using HTML and sending them as part of every e-mail)
- potential security issues of deluding the recipient to accept an email as being from an authoriative source (such as a bank) when this is not the case; this is related to phishing scams.
- potential security issues of simply rendering a complex format like HTML. For these reasons many mailing lists deliberately block HTML email either stripping out the HTML part to just leave the plain text part or rejecting the entire message.

External links

W3C Specifications

- [http://www.w3.org/TR/html401/ HTML 4.01 Specification]
- [http://www.w3.org/TR/xhtml1/ XHTML 1.0 Specification]
- [http://www.w3.org/TR/xhtml-media-types/ XHTML Media Types]

Validators

- [http://validator.w3.org/ W3C's Markup Validator]
- [http://www.htmlhelp.com/tools/validator/ WDG HTML Validator]
- [http://uitest.com/en/analysis/ Validators and checkers] ([http://uitest.com/en/check/ Site Check])

Selected Tutorials/Guides

- [http://www.yourhtmlsource.com/ HTMLSource: HTML Tutorials]
- [http://htmldog.com/ HTML Dog] Category:Markup languages Category:Technical communication Category:W3C standards Category:ISO standards ko:HTML ja:Hypertext Markup Language simple:HTML th:HTML

Typeface

In typography, a typeface consists of a co-ordinated set of grapheme (i.e., character) designs. A typeface is usually comprised of an alphabet of letters, numerals, and punctuation marks. Helvetica, Century Schoolbook, and Courier are three examples of typefaces. A typeface may also include or consist of ideograms and symbols (e.g., mathematical or map making glyphs). The art of designing typefaces, called type design, is the occupation of a type designer. In metal type, the word font denoted a complete typeface in a particular size (usually measured in points), one weight (e.g., light, book, bold, black), and one orientation (e.g., roman, italic, oblique). As regards digital type, the font is the computer file that stores the vector paths, before they are brought into being on a screen or a page. Digital fonts do contain unlimited (or application-limited) sizes. Some applications can provide additional weights or orientations of a font, but these are not considered typographically correct.

Introduction

A font, from Middle French fonte, meaning "(something that has been) melt(ed)" and referring to letters of a typeface produced by casting molten metal at a type foundry, consists of a set of glyphs (images) representing the characters from a particular character set in a particular typeface. Historically, fonts came in specific sizes (governing the actual height of the characters), and in sorts (governing the quantities of each letter provided). The design of a given character in a font took into account all these factors. In addition, as the spectrum of available designs and requirements of publishers has broadened over the centuries, fonts of specific weight (how dark the text appears—bold or light, for example) and additional specific conditions (most commonly "regular" as opposed to " italic" and/or "condensed") have led to "typeface families", collections of closely-related typeface designs that may include hundreds of styles. English-speaking printers have used the term fount for centuries to refer to the multipart device used (in its day) to assemble and print in a particular size and typeface design. Type foundries cast virtually all founts in various lead alloys from the 1450s until the middle of the 20th century, though wood served to make a few large founts (wood type), especially in the United States of America. In the 1890s mechanized typesetting emerged and began casting fonts on-the-fly in the form of lines of type of the size and length needed. This became known as "hot metal" type, and it remained profitable and widespread until its demise in the 1970s. The first machine of this type was the Linotype invented by Ottmar Mergenthaler. During a relatively brief transitional period (circa 1950s – 1990s), photographic technology, known as "phototypesetting", produced founts which came on rolls or discs of film. Photographic typesetting allowed for optical scaling, which meant that designers could produce multiple sizes from a single font (although physical constraints on the reproduction system used still required design-changes at different sizes — for example, ink traps and spikes to allow for spread of ink). Manually-operated phototypographic composition systems (using fonts made on rolls of film) allowed fine kerning between letters without great physical effort for the first time and spawned a large type-design industry in the 1960s and 1970s. The mid-1970s saw all of the major typeface technologies and all their fonts in use: from the original letterpress process of Gutenberg to mechanical metal typesetters, phototypositors, computer-controlled phototypesetters, and the earliest digital typesetters, (hulking machines with tiny processors and CRT outputs). From the mid-1980s, as digital typography has relentlessly grown, users have almost universally adopted the American spelling font, which nowadays nearly always means a computer file containing scalable, outline letterforms ("digital fonts"), usually in one of several common formats. Designers of some fonts, such as Microsoft's Verdana, intend their product primarily for use on computer screens. Digital fonts may encode the image of each character either as a bitmap, in a bitmap font, (seldom used since 1995) or by a higher-level description in terms of lines and curves enclosing a space (an outline font, also called a "vector font"). An outline "rasterizer" then fills the enclosed space of an outline font, deciding which pixels to represent as "black" and which as "white". The rasterization proceeds in straightforward fashion at higher resolutions (as for example in laser printers and in high-end publishing systems) but for screens, where each individual pixel can mean the difference between legibility and illegibility, digital fonts need hints included to make readable bitmaps at small sizes. Digital fonts today also contain data representing the "typography" used to compose them, including kerning pairs, component-creation data for accented characters, glyph-substitution rules for Arabic typography, and for connecting script faces and for simple everyday ligatures like "fl". (Common description languages that format digital type include PostScript, TrueType and OpenType. Enablers of these formats, including the rasterizers, appear in Microsoft and Apple Computer operating systems, Adobe Systems products and those of several other companies.)

Typeface anatomy

Typographers have derived a comprehensive vocabulary for describing and discussing the appearances of typefaces. Some vocabulary applies only to a subset of all scripts.

Diameter

Diameter symbol

Diameter

Diameter symbol

Geometry

The earliest geometry

The Greek period (c. 600 B.C. – 600 A.D.)

Thales and Pythagoras

Plato

Euclid

Archimedes

After Archimedes

The Middle Ages, Renaissance, and Reformation

The 17th and early 18th centuries

The late 18th and 19th centuries

Non-Euclidean geometry

Introduction of mathematical rigor

Analysis situs, or topology

The 20th century

See also

External links

Circle

Mathematical definitions

Properties

Chord properties

Tangent properties

Inscribed angle theorem

Secant, tangent, and chord properties

See also

External links

Length

Units of length(SI)

Other units of length

The Imperial and US customary units of length

Units are used in astronomy

See also

External links

RADIUS

Standards

See also

External links

Connected graph

Connections

Cuts

Examples

Properties

See also

Vertex

See also

Graph theory

History

Definition

Drawing graphs

Graphs as data structures

List structures

Matrix structures

Graph problems

Finding subgraphs

Graph coloring

Route problems

Network flow

Visibility graph problems

Covering Problems

Important algorithms

Related areas of mathematics

Applications

Subareas

Prominent graph theorists

Notes

See also

External links

Metric space

History

Definition

Examples

Metric spaces as topological spaces

Boundedness and compactness

Separation properties and extension of continuous functions

Distance between points and sets

Equivalence of metric spaces