| Home / lib / M_Mathematics / MA_Algebra / MAc_Combinatorics / | ||
Ore O. Theory of graphs (AMS, 1974)(K)(T)(279s)_MAc_.djvu |
|
Size 1.7Mb Date Dec 28, 2002 |
G.10.14) tpi^th fc=l,2,-,"
i=k /=*
where the non-increasing sequence {rj is the dual partition G.10.10) to the
partition {rj in G.10.9)...
One finds that this is the case only when each b e В is accessible from some
aeA and vice versa...
These directed subgraphs form a partial order when one writes
Я, => H2 if the edges in H2 belong to Я, and have the same directions...
This leaf compo-
composition graph is acyclic because a directed circuit in it would produce a directed
circuit in G passing through several leaves...
If Ko should exclude all edges of some H(jj'
there would be a graph Ku) in (8.4.2) with the same property contrary to the
assumption that all K(l) are generating graphs...
Conversely, it is evident that when in a bipartite graph G(V, V) there is a one-
to-one correspondence between the vertex sets it can be represented as a directed
graph in V...
] THEORY OF GRAPHS 161
are separating sets for G, that is, every edge has a vertex in one of them; these
particular separating sets have strong minimal properties corresponding to those
described in Theorem 7.9.2...
* Determine the largest number of edges in an acyclic basis graph defined
on a vertex set with n elements...
When the quadrilateral condition holds, simply related paths have the form
consequently both have the length 2...
As previously for acyclic graphs we say that a vertex b is an immediate successor
to a vertex a when a > b and there is no vertex с such that
a > о b;
in other words, the edge (a, ft) is essential...
The theory of lattices permeates large parts of mathematics, but it is beyond
the scope of this exposition to discuss these applications in any detail and the
reader is referred to the special works on this topic...
i i
Conversely, in a complete lattice the sets Г(а) of all x ^ a form an intersection
ring of sets, hence define a closure relation in the vertex set V...
To the set Vt
we introduce the product set
A0.4.2) V = Vl x V2 x - x Vk = x V,, iel
i
consisting of all fe-tuples
The orders {Qj define a partial order Q, the order product
A0.4.3) Q=xQt, iel
i
in the product set A0.4.2) in the sense of Section 2.6: When
w = (w1,w2,—,wk)
then v > w in Q if and only if for each i
where the equality does not hold for all indices...
Determine the maximal number of independent
elements in L and also an explicit Dilworth decomposition of L as the sum of
ordered sets...
The largest element in P contained in all p-, is the
cross-cut
But from
one concludes that
d=d...
The consequences of the theory of Galois connections follow, in particular:
Theorem 11.2.2...
When in the construc-
construction one follows a cross-edge C, in A2.1.7) the designated arcs A, and Aj indicate
on which arc one shall proceed in the next step...
In ana-
analyzing the matching theorems we made use of the concept of deficiency for a bi-
bipartite graph...
The edge covering number oce(G) is the smallest number of edges in any
covering graph H for G; the vertex covering number a.v(G) is the smallest
number of vertices in a covering set...
The same equality A3.3.3) holds also when Fis countable provided
the local degrees have a finite bound...
The graphs G0(n,k) satisfying A3.4.1) and having a mini-
minimal number of edges are the disjoint sum of к — 1 complete graphs
A3.4.2) G = Ct + ».+ C4_i...
Then the assumption that there should be
no convex polygons with m ^ 5 vertices leads to a contradiction, for according
to Ramsey's theorem when n ^ no(m) there would have to exist m points whose
4-combinations are all concave, contrary to the preceding observation for 5 points...
| © 2007 eKnigu | ||