User:Syp/temp2
A Wikipédiából, a szabad lexikonból.
This article presents the essential definitions. For a more complete account see gráf elmélet. For another use of the term "gráf" in mathematics, see gráf of a function.
A matematikában a gráf a gráfelmélet fő vizsgálati tárgya. Köznyelven megfogalmazva, a gráf csúcspontok halmaza, amik élekkel vannak összekötve. Alapértelmezett esetben irányítatlan gráfról beszélünk, tehát az A pontból B pontba húzott él ugyanaz, mint a B pontból A-ba húzott. Egy irányított gráfban vagy angolosan digráfban a két irányt megkülönböztetjük, irányított éleket használunk. Tipikusan a gráfot görbék által összekötött pontokként ábrázoljuk.
Tartalomjegyzék |
[szerkesztés] Definíciók
Definitions in gráfelmélet vary in the literature. The following are some of the more basic ways of defining gráf and related structures.
[szerkesztés] Irányítatlan gráfok
A gráf or irányítatlan gráf G is an ordered pair G := (V, E) that is subject to the following conditions:
-
- V is a set of csúcspont or nodes,
- E is a halmaz of unordered pairs of distinct csúcspont, called él or lines.
- The csúcspont belonging to an él are called the ends, endpoints, or end csúcspont of the él.
V (and hence E) are usually taken to be finite halmaz, and many of the well-known results are not true (or are rather different) for infinite gráfs because many of the arguments fail in the infinite case.
[szerkesztés] Irányított gráfok
A irányított gráf or digráf G is an ordered pair G:=(V, A) with
- V, a set of csúcspont or nodes,
- A, a halmaz of ordered pairs of csúcspont, called irányított él, arcs, or arrows. An él e = (x, y) is considered to be irányított from x to y; y is called the head and x is called the tail of the él.
A variation on this definition is the oriented gráf, which is a gráf (or multigráf; see below) with an orientation or direction assigned to each of its él. A distinction between a irányított gráf and an oriented simple gráf is that if x and y are csúcspont, a irányított gráf allows both (x, y) and (y, x) as él, while only egy is permitted in an oriented gráf. A more fundamental difference is that, in a irányított gráf (or multigráf), the directions are fixed, but in an oriented gráf (or multigráf), only the underlying gráf is fixed, while the orientation may vary.
A irányított körmentes gráf, also called a dag or DAG, is a irányított gráf with no irányított cycles.
A quiver is sometimes said to be simply a irányított gráf, but in practice it is a irányított gráf with vector spaces attached to the csúcspont and linear transformations attached to the arcs.
[szerkesztés] Vegyes gráf
A mixed gráf G is an ordered triple G := (V,E,A) with V, E and A defined as above.
[szerkesztés] Variations in the definitions
As defined above, él of irányítatlan gráf have distinct ends, and E and A are sets (with distinct elements, like all halmaz). Many applications require more general possibilities, but terminology varies.
A loop is an él (irányított or unirányított) with both ends the same; these may be permitted or not permitted according to the application. In this context, an él with two different ends is called a link.
Sometimes E and A are allowed to be multisets, so that there can be more than egy él between the same two csúcspont. Another way to allow multiple él is to make E a set, independent of V, and to specify the endpoints of an él by an incidence relation between V and E. The same applies to a irányított él halmaz A, except that there must be two incidence relations, egy for the head and egy for the tail of each él.
The unqualified word "gráf" might allow or disallow loops or multiple él in the literature, according to the preferences of the author and the requirements of the particular topic. If it is intended to exclude multiple él (and, in the unirányított case, to exclude loops), the gráf can be called simple. On the other hand, if it is intended to allow multiple él (and sometimes loops), the gráf can be called a multigráf. Sometimes the word pseudográf is used to indicate that both multiple él and loops are allowed. In exceptional situations it is even necessary to have él with only egy end, called halfél, or no ends (loose él); see for example signed gráfs.
[szerkesztés] Gráfok tulajdonságai
- For more definitions see Glossary of gráf elmélet.
Two él of a gráf are called szomszédos (sometimes coincident) if they share a common csúcspont. Similarly, two csúcspont are called szomszédos if they share a common él, that is they are joined by an él. An él and a csúcspont on that él are called incident.
The gráf with only egy csúcspont and no él is called the trivial gráf. A gráf with only csúcspont and no él is known as an élless gráf, empty gráf, or null gráf (there is no consistency in the literature). The gráf with no csúcspont and no él is sometimes called the null gráf or empty gráf, but not all mathematicians allow this object.
In a weighted gráf or digráf, each él is associated with some value, variously called its cost, weight, length or other term depending on the application; such gráf arise in many contexts, for example in optimal route problems such as the traveling salesman problem.
Normally, the csúcspont of a gráf, by their nature as elements of a set, are distinguishable. This kind of gráf may be called csúcspont-labeled. However, for many questions it is better to treat csúcspont as indistinguishable; then the gráf may be called unlabeled. (Of course, the csúcspont may be still distinguishable by the properties of the gráf itself, e.g., by the száms of incident él). If csúcspont are indistinguishable they may be distinguished by giving each csúcspont a label, hence the name csúcspont-labeled gráf. The same remarks apply to él, so that gráf which have labeled él are called él-labeled gráfs. gráf with labels attached to él or csúcspont are more generally designated as labeled. Consequently, gráf in which csúcspont are indistinguishable and él are indistinguishable are called unlabelled. (Note that in the literature the term labeled may apply to other kinds of labeling, besides that which serves only to distinguish different csúcspont or él.)
[szerkesztés] Példák

The picture is a gráfic representation of the following gráf
- V:={1,2,3,4,5,6}
- E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}
The fact that csúcspont 1 is szomszédos to csúcspont 2 is sometimes denoted by 1 ~ 2.
- In category elmélet a category can be considered a irányított multigráf with the objects as csúcspont and the morphisms as irányított él. The functors between categories induce then some, but not necessarily all, of the digráf morphisms.
- In computer science irányított gráf are used to represent finite state machines and many other discrete structures.
- A binary relation R on a halmaz X is a simple irányított gráf. Two él x,y of X are connected by an arrow if xRy.
[szerkesztés] Fontos gráfok
- In a complete gráf each pair of csúcspont is joined by an él, that is, the gráf contains all possible él.
- A planar gráf can be drawn in a plane (embedded in a plane) with no crossing él.
- A tree is a connected gráf with no cycles.
- Bipartite gráfs
- Perfect gráfs
- Cográfs
- Cayley gráfs
- The Petersen gráf and its generalizations
[szerkesztés] Gráfokon értelmezett műveletek
There are several operations that produce new gráf from old ones.
[szerkesztés] Unáris műveletek
- Line gráf
- Dual gráf
- Complement gráf
[szerkesztés] Bináris műveletek
- Cartesian product of gráfs
- Tensor product of gráfs
- Strong product of gráfs
- Lexicográfic product of gráfs
- Zig-zag product of gráfs
[szerkesztés] Általánosítások
In a hypergráf, an él can join more than two csúcspont.
An irányítatlan gráf can be seen as a simplicial complex consisting of 1-simplices (the él) and 0-simplices (the csúcspont). As such, complexes are generalizations of gráf since they allow for higher-dimensional simplices.
Every gráf gives rise to a matroid, but in general the gráf cannot be recovered from its matroid, so matroids are not truly generalizations of gráfs.
In model elmélet, a gráf is just a structure. But in that case, there is no limitation on the szám of él: it can be any cardinal szám.
[szerkesztés] Lásd még
- Polygon
- Tiling
- Glossary of gráf elmélet
- List of gráf elmélet topics
- gráf (data structure)
- gráf drawing
- Important publications in gráf elmélet
- Dual gráf
[szerkesztés] Külső hivatkozások
- gráf elmélet online textbook
- gráf elmélet tutorial
- gráf elmélet
- Some gráf elmélet algorithm animations
- Step through the algorithm to understand it.
- The compendium of algorithm visualisation sites
- Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum csúcspont Cover and csúcspont Coloring
- Image gallery no.1: Some real-life networks
- Image gallery no.2: More real-life gráfs
- gráf links collection
- Grafos spanish copyleft software
- Source code for computing neighbor shells in particle systems under periodic boundary conditions
- él Addition Planarity Algorithm — Online version of a paper that describes the Boyer-Myrvold planarity algorithm.
- él Addition Planarity Algorithm Source Code — Free C source code for reference implementation of Boyer-Myrvold planarity algorithm, which provides both a combinatorial planar embedder and Kuratowski subgráf isolator.

