Discrete Applied Mathematics98(2000)191–207
LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
Feodor F.Dragan a;?,Falk Nicolai b
a Universit a t Rostock,Fachbereich Informatik,A.Einstein Strasse21,D18051Rostock,Germany
b Kl o renstr.32,D46045Oberhausen,Germany
Received21July1997;revised18March1999;accepted5April1999
Abstract
For an undirected graph G the k th power G k of G is the graph with the same vertex set as G where two vertices are adjacent i their distance is at most k in G.In this paper we prove that every LexBFS-ordering of a distance-hereditary graph is both a common perfect elimination ordering of all even powers and a common semi-simplicial ordering of all powers of this graph. Moreover,we characterize those distance-hereditary graphs by forbidden subgraphs for which every LexBFS-ordering of the graph is a common perfect elimination ordering of all powers. As an application we present an algorithm which computes the diameter and a diametral pair of vertices of a distance-hereditary graph in linear time.?2000Elsevier Science B.V.All rights reserved.
Keywords:Distance-hereditary graphs;LexBFS-ordering;Perfect elimination ordering;Metric power;Diameter;Linear-time algorithm
1.Introduction
In recent years some papers investigating powers of certain graphs were published. One of the?rst results in this?eld is due to Duchet[10]:If G k is chordal then G k+2 is so.In particular,odd powers of chordal graphs are chordal,whereas even powers of chordal graphs are in general not chordal.In[1]it was shown that even powers of distance-hereditary graphs are chordal and odd powers do not contain a house,hole or domino as induced subgraph,i.e.they are HHD-free.
It is well known that every chordal graph has a perfect elimination ordering.Thus each chordal power of an arbitrary graph has a perfect elimination ordering.A nat-ural question is whether there is a common perfect elimination ordering of all(or First author supported by DFG and VW,Project No.I=69041,second author supported by DFG.
?Corresponding author.
E-mail addresses:dragan@informatik.uni-rostock.de(F.F.Dragan),falk.nicolai@t-online.de(F.Nicolai)
0166-218X/00/$-see front matter?2000Elsevier Science B.V.All rights reserved.
PII:S0166-218X(99)00157-2
192 F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207
some)chordal powers of a given graph.The?rst result in this direction using mini-
mal separators is given in[9]:If both G and G2are chordal then there is a common
perfect elimination ordering of these graphs.The existence of a common perfect elim-ination ordering of all chordal powers of an arbitrary given graph was proved in[4].
Such a common ordering can be computed in time O(|V||E|)using a generalized
version of Maximum Cardinality Search whichsimultaneously uses chordality of these
powers.
As shown in[18]lexicographic breadth-?rst-search(LexBFS)gives a perfect elimi-
nation ordering of a chordal graph in linear time.In[5]we proved that every LexBFS-
ordering of a chordal graph G gives a common perfect elimination ordering of all odd powers of G.Moreover,we characterized those chordal graphs by forbidden isomet-
ric subgraphs for which every LexBFS-ordering of the graph is a common perfect
elimination ordering of all powers.
In this paper we consider LexBFS-orderings of distance-hereditary graphs.Since
distance-hereditary graphs are House-Hole-Domino-free each LexBFS-ordering of G is
a semi-simplicial ordering of G[14,17].We will prove that every LexBFS-ordering of a distance-hereditary graph is both a common perfect elimination ordering of all even powers and a common semi-simplicial ordering of all powers of this graph.In [15]a tree structure for distance-hereditary graphs was given,i.e.distance-hereditary graphs were characterized as the graphs for which the family of all maximal connected cographs is a dual hypertree.It turns out that the dismantling scheme corresponding to this tree structure is a perfect elimination ordering of the square of the graph.Thus our results give another linear time method for computing such a dismantling scheme by only considering the graph itself.
Furthermore,we characterize those distance-hereditary graphs by forbidden sub-
graphs for which every LexBFS-ordering of the graph is a common perfect elimi-
nation ordering of all powers.For such graphs every LexBFS-ordering =(v1;:::;v n) is a‘diametral’ordering too,i.e.each vertex v i is diametral in the subgraph in-duced by{v i;:::;v n}.Such a special ordering is used in[16]for solving the prob-lems Hamiltonian circuit and path e ciently for distance-hereditary graphs.For gen-eral distance-hereditary graphs only a quadratic time for computing such an order-ing is known.But in the case of ptolemaic graphs(those graphs which are both chordal and distance-hereditary)our result leads to a linear time algorithm.Thus the Hamiltonian problems can be solved for ptolemaic graphs in linear time (cf.[16]).
Finally,as an application of the results of the?rst part of this paper,we present a
simple algorithm which computes both the diameter and a diametral pair of vertices of
a distance-hereditary graph in linear time.Note that in[7]a linear time algorithm for
computing the diameter of a distance-hereditary graph was presented,but that approach
is not usable for?nding a diametral pair of vertices.
Computing the diameter of a graph or a pair of diametral vertices is important in
network design.For example,by considering the routing problem in a network it is
obvious that for each single-source routing algorithm(i.e.given a vertex as source
F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207193 one has to reach all other vertices of the network)the lower bound of its running time is the diameter of the network.On the other hand,distance-hereditary graphs seem well suited for high reliable networks.Taking an k-connected distance-hereditary graph(k?2)as network the removal of at most k?1vertices(which corresponds to the failure of processors)does not change any distances(and thus routing times) within the network.
All these results show the usefulness of LexBFS-orderings not only for generat-ing special dismantling schemes of graphs,but also for solving certain optimization problems.
2.Preliminaries
Throughout this paper all graphs G=(V;E)are?nite,undirected,simple(i.e. loop-free and without multiple edges)and connected.
A path is a sequence of vertices v0;:::;v k such that v i v i+1∈E for i=0;:::;k?1; its length is k.As usual,an induced path of k vertices is denoted by P k.A graph G is connected i for every pair of vertices of G there is a path in G joining both vertices. The distance d G(u;v)of vertices u;v is the minimal length of a path connecting these vertices.If no confusion can arise we will omit the index G.
The eccentricity e(v)of a vertex v∈V is the maximum over d(v;x),x∈V.The minimum over the eccentricities of all vertices of G is the radius rad(G)of G,whereas the maximum is the diameter diam(G)of G.A pair x;y of vertices of G is called diametral i d(x;y)=diam(G).
The kth neighbourhood N k(v)of a vertex v of G is the set of all vertices of distance k to v,i.e.
N k(v):={u∈V:d G(u;v)=k};
whereas the disk of radius k centered at v is the set of all vertices of distance at most k to v:
k
N i(v):
D G(v;k):={u∈V:d G(u;v)6k}=
i=0
For convenience we will write N(v)instead of N1(v).Again,if no confusion can arise we will omit the index G.The kth power G k of G is the graph with the same vertex set V where two vertices are adjacent i their distance is at most k.
Next we recall the de?nition and some characterizations of the considered graph classes.An induced cycle is a sequence of vertices v0;:::;v k such that v0=v k and v i v j∈E i |i?j|=1(modulo k).The length|C|of a cycle C is its number of ver-tices.In the sequel a hole is an induced cycle of length at least?ve.A graph G is chordal i every induced cycle of G is of length three.One of the?rst results on chordal graphs is the characterization via dismantling schemes.A vertex v of G is called simplicial i D(v;1)induces a complete subgraph of G.A perfect elimination
194 F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207 ordering is an ordering of G such that v i is simplicial in G i:=G({v i;:::;v n})for each i=1;:::;n.It is well known that a graph is chordal if and only if it has a perfect elimination ordering(cf.[11]).Moreover,there is a linear time algorithm for comput-ing perfect elimination orderings of chordal graphs:Lexicographic breadth-?rst-search (LexBFS,[11]).To make the paper self-contained we present the rules of this algo-rithm.LexBFS orders the vertices of a graph by assigning numbers from n=|V|to1 in the following way:assign the number k to a vertex v(as yet unnumbered)which has lexically largest vector(s i:i=n;n?1;:::;k+1),where s i=1if v is adjacent to the vertex numbered i,and s i=0otherwise.An ordering =(v1;v2;:::;v n)of the vertex set of a graph G generated by LexBFS will be called LexBFS-ordering
of G.
In what follows we will often use the following property of LexBFS-orderings(cf.
[14]):
(P1)If a?b?c and ac∈E and bc∈E then there exists a vertex d
such that c?d;db∈E and da∈E:
We write x?y whenever in a given ordering vertex x has a smaller number than vertex y.Moreover,x?{y1;:::;y k}is an abbreviation for x?y i,i=1;:::;k.It is well known that any LexBFS-ordering has property(P1)[11].Moreover,any ordering ful?lling(P1)can be generated by LexBFS[5].
An induced subgraph H of G is an isometric subgraph of G i the distances within H are the same as in G,i.e.
?x;y∈V(H):d H(x;y)=d G(x;y):
A graph G is distance-hereditary[13]i each connected induced subgraph of G is iso-metric.Distance-hereditary graphs were extensively studied in[2,12,6,1,15].For prov-ing our results we will often use the following property:
Theorem2.1(The four point condition[2]).Let G be a distance-hereditary graph. Then;for every four vertices u;v;w;x at least two of the distance sums d(u;v)+d(w;x);d(u;w)+d(v;x);d(u;x)+d(w;v)
are equal;and;if the two smaller sums are equal then the larger one exceeds this by at most two.
Furthermore,distance-hereditary graphs can be characterized by forbidden subgraphs [2,12]:A graph is distance-hereditary if and only if it does not contain a hole,a house, a domino and a3-fan as induced subgraph(see Fig.1).
Finally,a graph G is called pseudo-modular[3]i for every three vertices x1;x2;x3 of G there are vertices z1;z2;z3of G such that
d(x i;x j)=d(x i;z i)+d(z i;z j)+d(z j;x j);i=j∈{1;2;3}
F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207195
Fig.1.A house,a domino and a3-fan.
and z1=z2=z3or{z1;z2;z3}is complete.In[3]it was shown that distance-hereditary graphs are pseudo-modular.
3.LexBFS-orderings and powers of distance-hereditary graphs
By de?nition,HHD-free graphs are the graphs which do not contain a hole,a house or a domino as induced subgraphs.These graphs were introduced in[14](see also [17])as the graphs for which every LexBFS-ordering of every induced subgraph is a semi-simplicial ordering.Hereby,a vertex is semi-simplicial i it is not a midpoint of a P4.A semi-simplicial ordering(v1;:::;v n)is an ordering of the vertex set of G such that v i is semi-simplicial in G i:=G({v i;:::;v n}).
In[8]we characterized HHD-free graphs by means of convexity.A subset S of V is called m3-convex i S contains every induced path of length at least three between vertices of S.Note that m3-convexity is a relaxation of m-convexity which is useful for characterizing chordal graphs.
Theorem3.1(Dragan et al.[8]).The following conditions are equivalent for a graph G:
(1)G is HHD-free.
(2)Every LexBFS-ordering of G is a semi-simplicial ordering.
(3)For every LexBFS-ordering(v1;:::;v n)of G the set V(G i)is m3-convex in G for all i=1;:::;n.
(4)The disks D(v;k);k?1;are m3-convex for all vertices v∈V.
For proving the results we will frequently use the following corollary of condition (3)of the above theorem:
Corollary3.2.If is a LexBFS-ordering of G and u1?···?u k is an induced path of length k?3then either u1or u k must be the leftmost vertex of the path with respect to .
The de?nition of semi-simplicial vertices immediately implies
196 F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207 Remark3.3.For each semi-simplicial vertex v of a graph G such that e(v)?2,the
subgraph G\{v}is isometric in G.
which forms the basis of the inductive proofs in the sequel.
3.1.Even powers of distance-hereditary graphs
In[1]it was proved that all even powers of a distance-hereditary graph are chordal.
In this section we show that any LexBFS-ordering of a given distance-hereditary graph
is a common perfect elimination ordering of all its even powers.
Lemma3.4.Each LexBFS-ordering of a distance-hereditary graph G is a perfect
elimination ordering of G2.
Proof.Let v be the?rst vertex of and assume that there are vertices x;y∈D(v;2)
such that d(x;y)?3.Since distance-hereditary graphs are HHD-free,v is semi-simplicial
in G,thus d(x;y)=3and x;y∈N2(v).Let a;b be adjacent vertices of N(v)such that ax∈E and by∈E.W.l.o.g.we may assume a?b.Now applying m3-convexity to
the induced path x?a?b?y gives min{x;y}?a.
Case1:x?a?y.We immediately conclude x?b.Applying(P1)to v?x?b
yields a vertex t?b adjacent to x but not to v.Since x is the smallest vertex of the path t?x?a?b this path cannot be induced by m3-convexity.Thus either ta∈E or tb∈E.Assuming tb∈E gives either a3-fan(for ta∈E)or a house(for ta∈E),a contradiction in both cases.Therefore tb∈E and ta∈E.But now the path t?a?b?y is induced and a is its smallest vertex,a contradiction to m3-convexity.
Case2:y?a?x.Analogously to Case1,applying(P1)to v?y?a gives a vertex s?a adjacent to y and b but neither to v nor to a.Thus the path s?b?a?x
F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207197 is induced and its minimum vertex is a,a contradiction to m3-convexity.
Case3:x;y?a.Since x?a and y?a we get vertices t and s as described in Cases1and2,respectively.Now the minimum vertex of the path t?a?b?s is a. By m3-convexity this path cannot be induced,implying st∈E.But now{s;t;a;b;v} induces a house.
Induction and Remark3.3settle the proof.
Theorem3.5.Each LexBFS-ordering of a distance-hereditary graph G is a perfect elimination ordering of each even power G2k;k?1.
Proof.By Remark3.3it is su cient to prove that the?rst vertex of a LexBFS-ordering is simplicial in G2k.This we show by induction on k.
For k=1we are done by Lemma3.4.So we may assume k?2.Let v be the?rst vertex of and assume that there are vertices x;y∈D(v;2k)such that d(x;y)?2k+1. By the induction hypothesis v is simplicial in the even powers G2;:::;G2k?2.In par-ticular,the distance between any two vertices of D(v;2k?2)is at most2k?2.We conclude x;y∈D(v;2k?2)and d(x;y)62k+2.Moreover,both vertices x and y cannot be in N2k?1(v),since otherwise d(x;y)62k will hold.
Case1:x∈N2k(v)and y∈N2k?1(v).Choose vertices a1;b∈N2k?2(v)and a2∈N2k?1(v)rightmost in such that a1?a2?x induces a P3and yb∈E.We immediately obtain the following equalities:
d(a1;b)=2k?2;d(a2;b)=d(a1;y)=2k?1;
d(a2;y)=2k;d(x;y)=2k+1:
By pseudo-modularity of G there is a vertex u such that
d(v;u)=d(u;a1)=d(u;b)=k?1:
Let z be the neighbour of v on a shortest path joining v and u and i its position in .We obtain
d(z;a1)=d(z;b)=2k?3and d(z;a2)=d(z;y)=2k?2:
198 F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207
Since d(a2;y)=2k,a2;y∈D(z;2k?2)and z is simplicial in G2k?2
i not both vertices
a2;y can be contained in G i,i.e.min{a2;y}?z.
Case1.1:y?z?a2.Applying(P1)to v?y?z gives a vertex t?z adjacent to y but not to v.Let b?w1?···?w l?z be a shortest path joining b and z and de?ne P:=t?y?b?w1?···?w l?z.Since|P|?3and y is smaller than t and z the path P cannot be induced by m3-convexity,i.e.tb∈E or tw1∈E.We conclude 2k?36d(z;t)62k?2.Thus both vertices a2and t are in D(z;2k?2)in G i.But d(a2;y)=2k and yt∈E imply d(a2;t)?2k?1,a contradiction to the simpliciality of z in G2k?2
i
.
Case1.2:a2?z.Let a1?w1?···?w l?z be a shortest path joining a1and z.Since a2?z and the length of the induced path x?a2?a1?w1?···?w l?z is at least three m3-convexity implies x?a2.Now applying(P1)to v?x?z gives a vertex t?z adjacent to x but not to v.Since x is smaller than t and z the path t?x?a2?a1?w1?···?w l?z cannot be induced by m3-convexity.Hence,by distance requirements ta1∈E or ta2∈E.If ta1∈E then ta2∈E and the path t?a2?a1?w1?···?w l?z is induced.This implies a contradiction to m3-convexity since a2is smaller than t and z.Therefore ta1∈E.But now we can replace a2by t?a2, a contradiction to the choice of a2.
Case2:x;y∈N2k(v).Choose vertices a1;b1∈N2k?2(v)and a2;b2∈N2k?1(v)such that a1?a2?x and b1?b2?y are induced paths.Since we already handled Case1 we may assume d(a2;y);d(b2;x)=2k+1.We immediately conclude
d(a2;y)=d(b2;x)=2k and d(x;y)=2k+1:
F.F.Dragan,F.Nicolai /Discrete Applied Mathematics 98(2000)191–207199
Now consider the distance sums of the vertices v;x;y;a 1:
d (v;x )+d (a 1;y )=2k +d (a 1;y )?4k ?1;
d (v;a 1)+d (x;y )=4k ?1;
d (v;y )+d (a 1;x )=2k +2:
The four-point condition now implies
d (v;x )+d (a 1;y )=d (v;a 1)+d (x;y )=4k ?1:
Thus d (a 1;y )=2k ?1and by symmetry d (b 1;x )=2k ?1.So we can compute the distance sums for x;y;a 1;b 1:
d (a 1;x )+d (b 1;y )=4;
d (a 1;b 1)+d (x;y )=2k +1+d (a 1;b 1)?4k ?2;
d (a 1;y )+d (b 1;x )=4k ?2:
The four-point condition gives
d (a 1;b 1)+d (x;y )=d (a 1;y )+d (b 1;x )=4k ?2
and thus d (a 1;b 1)=2k ?3.This immediately implies d (a 2;b 2)=2k ?1.From d (a 1;b 1)=2k ?3and d (v;a 1)=d (v;b 1)=2k ?2pseudo-modularity yields pairwise adjacent vertices u 1;u 2;u 3such that
d (v;u 1)=k ?1and d (a 1;u 2)=d (b 1;u 3)=k ?2:
Let z be the neighbour of v on a shortest path joining v and u 1and i its position in .Then
d (z;a 1)=d (z;b 1)=2k ?3and d (z;a 2)=d (z;b 2)=2k ?2:
Therefore the vertices a 2;b 2are contained in D (z;2k ?2).By induction hypothesis z is simplicial in G 2k ?2i .Thus d (a 2;b 2)=2k ?1implies min {a 2;b 2}?z .Due to symmetry we may assume a 2?z .Let a 1?w 1?···?w l ?z be a shortest path joining a 1and z .Since a 2?z and the length of the induced path x ?a 2?a 1?w 1?···?w l ?z is at least three m 3-convexity implies x ?a 2.Now (P1)applied to v ?x ?z yields a vertex t ?z adjacent to x but not to v (note t =a 2since a 2?z ?t ).Since vertex x is smaller than the endvertices t;z of the path t ?x ?a 2?a 1?w 1?···?w l ?z we conclude ta 2∈E or ta 1∈E by m 3-convexity.If ta 1∈E then ta 2∈E and the path t ?a 2?a 1?w 1?···?w l ?z is induced.But a 2is smaller than t and z ,a contradiction to the m 3-convexity.Therefore ta 1∈E which immediately implies d (z;t )=2k ?2and d (t;b 2)=2k ?1.
If b 2?z then both vertices b 2and t are contained in D (z;2k ?2)in G i ,a contradic-tion to the simpliciality of z in G 2k ?2i .If b 2?z then we can apply the same arguments as above to b 2;b 1;y yielding a vertex s ?z adjacent to y and b 1with d (z;s )=2k ?2.From tx ∈E ,sy ∈E and d (x;y )=2k +1we conclude d (s;t )?2k ?1.But both s and t are contained in D (z;2k ?2)in G i ,again a contradiction to the simpliciality of z in G 2k ?2i .
200 F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207
Fig.2.A C(k)4and a C(1)4minus a pendant vertex.
3.2.Odd powers of distance-hereditary graphs
In[1]it was proved that all odd powers of a distance-hereditary graph are HHD-free. Moreover,an odd power G2k+1is chordal if and only if G does not contain an induced subgraph isomorphic to the C(k)4,cf.Fig.2A.
Theorem3.6.Each LexBFS-ordering of a given distance-hereditary graph G is a common perfect elimination ordering of all its powers if and only if G does not contain the graph of Fig.2B as induced subgraph.
Proof.Assume that a distance-hereditary graph G contains the graph of Fig.2B as induced subgraph.We will construct a LexBFS-ordering of G which is not a per-fect elimination ordering of its cube.We start the LexBFS-procedure at the vertex labeled by n.Let the labels of the graph of Fig.2B be given by .Obviously, {a;d}?p?n?1?n and c?b.Suppose a?b and let i be the position of a in .Then a is not simplicial in(G i)2since a?{b;p},b;p∈D(a;2)and d(b;p)=3. Thus c?b?a?p?n?1?n.Now we will show d?c which implies that d is not simplicial in(G j)3where j is the position of d in .Assume c?d.Applying(P1) to c?d?p gives a vertex t?p adjacent to d but not to c.Since t?p we have t=a,and tn∈E by the rules of LexBFS.But this is a contradiction to d(n;d)=3. To prove the converse let G be a distance-hereditary graph which does not contain the graph of Fig.2B.By Theorem3.5it is su cient to show by induction on k that is a perfect elimination ordering for G2k+1;k?1.By Remark3.3we have only to prove that the?rst vertex v of is simplicial in G2k+1.We start with the cube of G. Assume that there are vertices x;y∈D(v;3)such that d(x;y)?4.Since v is simplicial in G2by Theorem3.5we immediately have
d(v;x)=d(v;y)=3and d(x;y)=4:
F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207201 Choose vertices a;b∈N2(v)rightmost in such that ax∈E and by∈E.Since v is simplicial in G2and d(x;y)=4we must have
d(a;b)=2and d(a;y)=d(b;x)=3:
Thus,by pseudo-modularity there is a vertex u∈N(v)adjacent to v;a;b.We may choose u rightmost in .Let i be the position of u in .W.l.o.g.we may assume a?b.Since the path x?a?u?b is induced and a?b m3-convexity gives x?a.On the other hand,both vertices a and y are contained in D(u;2).Since d(a;y)=3and u is simplicial in G2i we must have a?u or y?u.Assuming a?u immediately gives x?u.Thus(P1)applied to v?x?u yields a vertex t?u adjacent to x but not to v. Note t=a.Now vertices x and a are smaller than t,u and b.Thus m3-convexity with respect to the path t?x?a?u?b implies tu∈E.Therefore,we can replace a by t?a,a contradiction to the choice of a.Consequently,y?u?a holds.Property(P1) applied to u?a?b yields a vertex t?b adjacent to a but not to u.Since u is smaller than the endvertices t;b of the path t?a?u?b and tu∈E we infer tb∈E from m3-convexity.By distance requirements t cannot be adjacent to x and y.If tv∈E then we can replace u by t?u,a contradiction to the choice of u.Thus tv∈E and we have constructed an induced subgraph isomorphic to the graph of Fig.2B,a contradiction. Consequently,v is simplicial in G3.
Now let k?2and assume that there are vertices x;y in D(v;2k+1)such that d(x;y)?2k+2.Since v is simplicial in G2k by Theorem3.5there must be vertices a;b∈N2k(v)such that
d(a;b)=2k;d(v;x)=d(v;y)=2k+1;d(x;y)=2k+2and ax;by∈E: We may choose a and b rightmost in and assume a?b by symmetry.Now we have d(v;a)=d(v;b)=d(a;b)=2k and thus pseudo-modularity gives a vertex u such that d(v;u)=d(a;u)=d(b;u)=k:
Let z be the neighbour of v on a shortest path joining v and u and i its position in .By the induction hypothesis z is simplicial in G2k?1.Since a;b∈D(z;2k?1)but d(a;b)=2k we must have a?z.Let a?w1?···?w l?z be a shortest path joining a and z.Since a?z m3-convexity with respect to x?a?w1?···?w l?z yields x?a?z.Applying(P1)to v?x?z gives a vertex t?z adjacent to x but not to v.Note t=a.Now the path t?x?a?w1?···?w l?z cannot be induced by m3-convexity.By distance requirements the only possible chords are ta and tw1.If tw1∈E then ta∈E and t?a?w1?···?w l?z is induced.But a is smaller than t and z,a contradiction to m3-convexity.Thus tw1∈E and we can replace a by t?a, a contradiction to the choice of a.
Finally,using the four point condition and Theorem3.5we show
Theorem3.7.Every LexBFS-ordering of a distance-hereditary graph G is a common semi-simplicial ordering of all its powers.
202 F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207
Proof.Since each distance-hereditary graph is HHD-free and each perfect elimination ordering is a semi-simplicial ordering the result holds for G and all even powers. Again,by Remark3.3it is su cient to consider the?rst vertex v of .Assume that v is a midpoint of a P4x?v?y?w in G2k+1;k?1.Since v is simplicial in G2k we have
d(a;b)=2k;d(v;x)=d(v;y)=2k+1;d(x;y)=2k+2and ax;by∈E
for some vertices a;b∈N2k(v).By pseudo-modularity there is a vertex z such that
d(v;z)=d(a;z)=d(b;z)=k:
To apply the four-point condition we compute the distance sums of the vertices v;y;z;w:
d(v;z)+d(y;w)=k+d(y;w)63k+1;
d(v;y)+d(z;w)=2k+1+d(z;w)?3k+2;
d(v;w)+d(z;y)=k+1+d(v;w)?3k+2:
Thus the second and third sum must be equal giving d(z;w)+k=d(v;w).Since d(z;v)=k we obtain d(v;w)=d(v;z)+d(z;w),i.e.z lies on a shortest path joining v and w.We proceed by considering x;y;z;w:
d(x;z)+d(y;w)=k+1+d(y;w)63k+2;
d(x;w)+d(z;y)=k+1+d(x;w)?3k+2;
d(x;y)+d(z;w)=2k+2+d(z;w)?3k+3:
Thus the second and third sum must be equal giving d(x;w)=k+1+d(z;w).Since d(z;x)=k+1we obtain d(x;w)=d(x;z)+d(z;w),i.e.z lies on a shortest path joining x and w.
Let c be a vertex in N2k+2(v)which lies on a shortest path joining z and w,i.e. d(z;w)=d(z;c)+d(c;w).By Theorem3.5vertex v is simplicial in G2k+2.Thus,from c;x∈D(v;2k+2)we conclude d(x;c)62k+2.Now we obtain a contradiction by the following inequalities:
d(x;w)6d(x;c)+d(c;w)62k+2+d(c;w);
d(x;w)=d(x;z)+d(z;w)=d(x;z)+d(z;c)+d(c;w)=2k+3+d(c;w)
which is impossible.
https://www.doczj.com/doc/8911687053.html,puting a diametral pair of vertices
In this section we apply the preceding results to compute the diameter and a diametral pair of vertices of a distance-hereditary graph in linear time.
F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207203 Lemma4.1.Let v be the?rst vertex of a LexBFS-ordering of a distance-hereditary graph
G.Then
diam(G)?16e(v)6diam(G):
Moreover;if e(v)is even then e(v)=diam(G).
Proof.If e(v)=2k;k?1,then G2k is complete by Theorem3.5,and thus diam(G)=2k. If e(v)=2k+1;k?1,then G2k+2is complete by Theorem3.5,and hence2k+16 diam(G)62k+2.
Corollary4.2.Let G be a distance-hereditary graph which does not contain the graph of Fig.2B as induced subgraph;and let v be the?rst vertex of a LexBFS-ordering of G.Then e(v)=diam(G).
Proof.Immediately follows from Theorem3.6and the proof of Lemma4.1.
For the sequel we may assume that G is not complete for otherwise there is nothing to do.In what follows we describe the steps of the algorithm.
At?rst we compute a LexBFS-ordering of a given distance-hereditary graph G. Let v be the?rst vertex of .If e(v)=2k;k?1,then,by Lemma4.1,e(v)=diam(G), and the vertices v and w∈N e(v)(v)form a diametral pair of G.So let e(v)=2k+1. Now we start LexBFS at vertex v yielding a LexBFS-ordering with?rst vertex u.If e(u)=2k+2then,by Lemma4.1,diam(G)=2k+2and the vertices u and w∈N e(u)(u) form a diametral pair of G.Otherwise(e(v)=e(u)=2k+1)we choose a vertex z at distance k to u and at distance k+1to v.
Lemma4.3.k+16e(z)6k+2.
Proof.Since d(z;v)=k+1we immediately have e(z)?k+1.So let w be a vertex of V such that d(z;w)?k+2.We obtain the following distance sums: d(u;v)+d(z;w)=2k+1+d(z;w)?3k+3;
d(u;z)+d(v;w)=k+d(v;w)63k+1;
d(u;w)+d(v;z)=k+1+d(u;w)63k+2:
Now the four-point condition gives
d(v;w)=2k+1;d(u;w)=2k and d(z;w)=k+2:
This settles the proof.
For every vertex w of V\D(z;k)we store in track(w)the second edge of an arbitrary shortest path from z to w.De?ne F:={track(w):w∈V\D(z;k)}.We will say that two edges in a graph are independent i the vertices of this edges induce a2K2in G.
204 F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207
Lemma4.4.diam(G)=2k+2if and only if the set F contains two independent edges.
Proof.Let diam(G)=2k+2and let x;y be vertices of G such that d(x;y)=2k+2. Since both u and v(as?rst vertices of LexBFS-orderings)are simplicial in G2k we get
d(u;x)=d(u;y)=d(v;x)=d(v;y)=2k+1:
With d(z;u)=k this implies d(z;x)?k+1.So we obtain the following distance sums:
d(u;v)+d(z;x)=2k+1+d(z;x)?3k+2;
d(u;z)+d(v;x)=k+2k+1=3k+1;
d(u;x)+d(v;z)=2k+1+k+1=3k+2:
Now the four-point condition gives d(z;x)=k+1.By symmetry,d(z;y)=k+1. Thus z lies on a shortest path joining x and y.Obviously,track(x)and track(y)are independent edges due to d(x;y)=2k+2and d(x;z)=d(y;z)=k+1.
Now let s1s2and t1t2be independent edges in F.Let z?s1?s2?···?w1and z?t1?t2?···?w2be shortest paths of length at least k+1.We will prove d(w1;w2)= 2k+2.Since s2?s1?z?t1?t2is induced we get d(s2;t2)=https://www.doczj.com/doc/8911687053.html,ing Lemma4.3 we obtain the following distance sums:
d(w1;z)+d(s2;t2)=4+d(w1;z)∈{k+5;k+6};
d(w1;s2)+d(z;t2)=2+d(w1;s2)∈{k+1;k+2};
d(w1;t2)+d(z;s2)=2+d(w1;t2):
Since the di erence between the?rst and second distance sum is at least three the four-point condition implies that the larger two sums must be equal,i.e.the?rst and third one.So we get
k+36d(w1;t2)6k+4and k+36d(w2;s2)6k+4
by symmetry.Together with d(s2;t2)=4this implies
d(w1;w2)+d(s2;t2)=4+d(w1;w2);
d(w1;s2)+d(w2;t2)∈{2k?2;2k?1;2k};
d(w1;t2)+d(w2;s2)∈{2k+6;2k+7;2k+8}:
By the same argument as above the four-point condition implies that the?rst and the third distance sum must be equal,i.e.d(w1;w2)?2k+2.
Therefore,the following algorithm correctly computes the diameter and a diametral pair of a distance-hereditary graph:
F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207205
Fig.3.Algorithm DHGDiam—Examples.
Algorithm DHGDiam.
Input:A connected distance-hereditary graph G.
Output:diam(G)and a diametral pair of vertices of G.
(1)begin :=LexBFS(G;s)for some s∈V(G).
(2)Let v be the?rst vertex of .
(3)if e(v)is even then return(e(v);(v;w))where w∈N e(v)(v).
(4)else :=LexBFS(G;v).
(5)Let u be the?rst vertex of .
(6)if e(u)=e(v)+1then return(e(u);(u;w))where w∈N e(u)(u).
(7)else Let k∈N such that e(v)=e(u)=2k+1.
(8)Choose a vertex z from D(u;k)∩D(v;k+1).
(9)F:={track(w):w∈V\D(z;k)}.
(10)if F contains a pair e1;e2of independent edges
(11)then return(2k+2;(x;y))
where x;y∈V such that track(x)=e1and track(y)=e2.
(12)else return(2k+1;(v;u))
(13)end.
Before going into the implementation details consider the examples of Fig.3.In the ?rst one,a C(1)4minus a pendant vertex,the algorithm correctly stops in step(6).In the second one both?rst vertices of both LexBFS-ordering s have odd eccentricity. Thus we must compute the track-values and the set F.
206 F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207
It remains to show that the above algorithm can be implemented in linear time.It
is well known that LexBFS and BFS run in linear time.So it is su cient to consider steps(9)and(10).
Step(9):At?rst we build a BFS-tree rooted at z yielding the set of neighbourhoods
N i(z);i=0;:::;e(z)of z.For any vertex x∈V\{z}let f(x)denote the father of x in the BFS-tree.We compute the track-values levelwise:For all vertices w in N2(z)de?ne
track(w):=wy where y=f(w).Recursively,we compute track(w):=track(f(w))for w∈N i(z),i=3;:::;e(z).Now we can compute F by collecting all track-edges of the vertices of the set V\D(z;k).Obviously,the above procedure runs in linear time. Step(10):We use the BFS-tree rooted at z which was already computed in step (9).Let b:V→N be the numbering of the vertices of G produced by BFS where b(z)=1.Let S1(S2)be the vertices of N(z)(N2(z))which are endpoints of edges of F.Furthermore,for all vertices y of S1let C(y)be the set of children of y in the BFS-tree contained in S2,i.e.C(y)={w∈S2:y=f(w)}.De?ne c(y):=|C(y)|. Obviously,the sets S1;S2and the values c(y)for y∈S1can be computed in linear time.
In what follows we explain a procedure looking for a pair of independent edges:
Consider the vertex x of S1with maximal b-number.Stepping through the neigh-bourhood of x we mark all vertices y of S1which are either neighbours of x or every BFS-child of y in S2is adjacent to x,i.e.C(y)?N(x).
We show that this can be done in O(deg(x))by using a counter m(y)for each vertex y of S1counting the neighbours of x in C(y).Initially,m(y)=0for all y∈S1. The algorithm steps three times through the neighbourhood of x and thus runs in O(deg(x))time:
?For every neighbour w of x do:
If w∈S1then mark w.
If w∈S2then increase the counter m of f(w)by1.
?For every neighbour w of x do:
If w∈S2and c(f(w))=m(f(w))then mark f(w).
?For every neighbour w of x do:
If w∈S2then reset the counter m of f(w)to zero.
If there is an unmarked vertex y∈S1then xy∈E and there must be a BFS-child w
of y in S2not adjacent to x.We claim that the edges yw and xu,for some neighbour
u of x in S2,are independent(note that x∈S1implies that there is some vertex u∈S2
F.F.Dragan,F.Nicolai/Discrete Applied Mathematics98(2000)191–207207 with x=f(u)by the de?nitions of S1and S2).Indeed,since b(x)?b(y)and x=f(u) the rules of BFS imply uy∈E(if uy∈E then f(u)=y).Now uw∈E for otherwise the set{z;x;y;w;u}induces a cycle of length?ve.Therefore,the edges yw and xu are independent.
Now assume that all vertices of S1are marked.Then,by the rules of the marking algorithm,x cannot be an endpoint of a pair of independent edges.So we delete x from S1and all neighbours of x in S2.We repeat the above procedure until we get a pair of independent edges or S1is empty.
Since the processing of a vertex x of S1takes O(deg(x))the total running time of step(10)is linear.
Summarizing the above we get
Theorem4.5.For distance-hereditary graph s the diameter and a diametral pair of vertices can be computed in linear time.
References
[1]H.J.Bandelt,A.Henkmann,F.Nicolai,Powers of distance-hereditary graphs,Discrete Math.145(1995)
37–60.
[2]H.-J.Bandelt,H.M.Mulder,Distance-hereditary graphs,https://www.doczj.com/doc/8911687053.html,bin.Theory(B)41(1986)182–208.
[3]H.-J.Bandelt,H.M.Mulder,Pseudo-modular graphs,Discrete Math.62(1986)245–260.
[4]A.Brandst a dt,V.D.Chepoi,F.F.Dragan,Perfect elimination orderings of chordal powers of graphs,
Discrete Math.158(1996)273–278.
[5]A.Brandst a dt,F.F.Dragan,F.Nicolai,LexBFS-orderings and powers of chordal graphs,Discrete Math.
171(1997)27–42.
[6]A.d’Atri,M.Moscarini,Distance-hereditary graphs,Steiner trees and connected domination,SIAM J.
Comput.17(1988)521–538.
[7]F.F.Dragan,Dominating cliques in distance-hereditary graphs,Proceedings of SWAT’94,Springer
Lecture Notes in Computer Science,vol.824,pp.370–381.
[8]F.F.Dragan,F.Nicolai,A.Brandst a dt,Convexity and HHD-free graphs,SIAM J.Discrete Math.12
(1999)119–135.
[9]F.F.Dragan,C.F.Prisacaru,V.D.Chepoi,Location problems in graphs and the Helly property,Discrete
Math.Moscow4(1992)67–73(in Russian).
[10]P.Duchet,Classical perfect graphs,Ann.Discrete Math.21(1984)67–96.
[11]M.C.Golumbic,Algorithmic Graph Theory and Perfect Graphs,Academic Press,New York,1980.
[12]P.L.Hammer,F.Ma ray,Completely separable graphs,Discrete Appl.Math.27(1990)85–99.
[13]E.Howorka,A characterization of distance-hereditary graphs,Quart.J.Math.Oxford Ser.2(28)(1977)
417–420.
[14]B.Jamison,S.Olariu,On the semi-perfect elimination,Adv.App.Math.9(1988)364–376.
[15]F.Nicolai,A hypertree characterization of distance-hereditary graphs,Technical Report Gerhard-
Mercator-Universit a t-Gersamthochule Duisburg SM-DU-255,1994.
[16]F.Nicolai,Hamiltonian problems on distance-hereditary graphs,Technical Report
Gerhard-Mercator-Universit a t-Gersamthochule Duisburg SM-DU-264,1994.
[17]S.Olariu,Some aspects of semi-perfect elimination,Disc.Appl.Math.31(1991)291–298.
[18]D.Rose,R.E.Tarjan,G.Lueker,Algorithmic aspects on vertex elimination on graphs,SIAM https://www.doczj.com/doc/8911687053.html,put.
5(1976)266–283.
如何写先进个人事迹 篇一：如何写先进事迹材料 如何写先进事迹材料 一般有两种情况：一是先进个人，如先进工作者、优秀党员、劳动模范等；一是先进集体或先进单位，如先进党支部、先进车间或科室，抗洪抢险先进集体等。无论是先进个人还是先进集体，他们的先进事迹，内容各不相同，因此要整理材料，不可能固定一个模式。一般来说，可大体从以下方面进行整理。 (1)要拟定恰当的标题。先进事迹材料的标题，有两部分内容必不可少，一是要写明先进个人姓名和先进集体的名称，使人一眼便看出是哪个人或哪个集体、哪个单位的先进事迹。二是要概括标明先进事迹的主要内容或材料的用途。例如《王鬃同志端正党风的先进事迹》、《关于评选张鬃同志为全国新长征突击手的材料》、《关于评选鬃处党支部为省直机关先进党支部的材料》等。 (2)正文。正文的开头，要写明先进个人的简要情况，包括：姓名、性别、年龄、工作单位、职务、是否党团员等。此外，还要写明有关单位准备授予他(她)什么荣誉称号，或给予哪种形式的奖励。对先进集体、先进单位，要根据其先进事迹的主要内容，寥寥数语即应写明，不须用更多的文字。 然后，要写先进人物或先进集体的主要事迹。这部分内容是全篇材料
的主体，要下功夫写好，关键是要写得既具体，又不繁琐；既概括，又不抽象；既生动形象，又很实在。总之，就是要写得很有说服力，让人一看便可得出够得上先进的结论。比如，写一位端正党风先进人物的事迹材料，就应当着重写这位同志在发扬党的优良传统和作风方面都有哪些突出的先进事迹，在同不正之风作斗争中有哪些突出的表现。又如，写一位搞改革的先进人物的事迹材料，就应当着力写这位同志是从哪些方面进行改革的，已经取得了哪些突出的成果，特别是改革前后的．经济效益或社会效益都有了哪些明显的变化。在写这些先进事迹时，无论是先进个人还是先进集体的，都应选取那些具有代表性的具体事实来说明。必要时还可运用一些数字，以增强先进事迹材料的说服力。 为了使先进事迹的内容眉目清晰、更加条理化，在文字表述上还可分成若干自然段来写，特别是对那些涉及较多方面的先进事迹材料，采取这种写法尤为必要。如果将各方面内容材料都混在一起，是不易写明的。在分段写时，最好在每段之前根据内容标出小标题，或以明确的观点加以概括，使标题或观点与内容浑然一体。 最后，是先进事迹材料的署名。一般说，整理先进个人和先进集体的材料，都是以本级组织或上级组织的名义；是代表组织意见的。因此，材料整理完后，应经有关领导同志审定，以相应一级组织正式署名上报。这类材料不宜以个人名义署名。 写作典型经验材料-般包括以下几部分： (1)标题。有多种写法，通常是把典型经验高度集中地概括出来，一
常用兽药原粉汇总 原粉名称 适应症 安乃近临床上常用于猪附红细胞体、链球菌、弓形体、圆环病毒、 蓝耳病、猪瘟、猪丹毒等病引起的体温升高，有明显的解 热镇痛作用。鸡的禽流行性感冒、新城疫、法氏囊等引起 的体温升高，能迅速解除症状。 地美硝唑主要用于禽弧菌性肝炎、坏死性组织、火鸡组织滴虫病、 禽的毛滴虫病等，对牛的毛滴虫病也有很好的疗效。 氟苯尼考主要用于治疗： 1：猪：猪传染性萎缩性鼻炎、猪呼吸疲乏综合症（PRDC）、 传染性胸膜肺炎、气喘病、肺疫、仔猪黄白痢、副伤寒； 猪瘟、蓝耳病、乙型脑炎等引起的继发感染； 2：禽：慢性呼吸道病、气囊炎、鸭传染性浆膜炎、霍乱、 大肠杆菌病、沙门氏菌病；鸡新城疫、禽流感等引起的 继发； 3：水产类：由弧菌，链球菌，假单胞菌，爱德华氏菌， 产气单胞菌引起的虾的红腿病，幼体菌血症，甲壳溃疡病， 黑鳃和烂鳃病，丝状细菌病，河蟹的烂肢病，水霉病，颤 抖病，鱼的弧菌病，出血病、肠炎、赤皮、烂尾、腐皮等 细菌性爆发病。 黄芪多糖主要用于抗病毒，提高机体免疫力，如新城疫、法氏囊、 喉气管炎等疾病；对猪圆环病毒、蓝耳病、传染性胃肠炎、 肝炎等疾病有防治作用 磺胺间甲氧嘧啶钠主要用于治疗和预防各种敏感菌引起的呼吸道、消化道、 泌尿道感染及球虫病、猪弓形虫病、猪水肿病、鸡住白细 胞虫病、猪萎缩性鼻炎。局部灌注可治疗乳腺炎和子宫内 膜炎；水产类敏感菌所致的肺炎，出血性败血症。 磺胺氯吡嗪钠本品属磺胺类药物，具有性质稳定，抗菌谱较广，水溶性 好等优点。口服有效，并能很快分布至其它器官。主要用 于抗球虫病。 甲磺酸左旋氧氟沙 星本品主要用于治疗由敏感菌引起的畜禽呼吸系统、泌尿生殖系统、皮肤软组织、消化系统疾病。如禽的大肠杆菌病、沙门氏菌病、传染性鼻炎、鸡奇异变形杆菌病、葡萄球菌病、鸭疫巴氏杆菌病、禽霍乱、慢性呼吸道病、仔猪的喘气病、仔猪黄、白痢、仔猪副伤寒、牛传染性胸膜肺炎、牛出败、牛弧菌性疾病、牛流行性腹泻、羔羊疾病、传染 性胃肠炎等 甲硝唑主要用于禽弧菌性肝炎、坏死性肠炎、火鸡组织滴虫病、禽的毛滴虫病等，对牛的毛滴虫病也有很好的疗效。
How to manage time Time treats everyone fairly that we all have 24 hours per day. Some of us are capable to make good use of time while some find it hard to do so. Knowing how to manage them is essential in our life. Take myself as an example. When I was still a senior high student, I was fully occupied with my studies. Therefore, I hardly had spare time to have fun or develop my hobbies. But things were changed after I entered university. I got more free time than ever before. But ironically, I found it difficult to adjust this kind of brand-new school life and there was no such thing called time management on my mind. It was not until the second year that I realized I had wasted my whole year doing nothing. I could have taken up a Spanish course. I could have read ten books about the stories of successful people. I could have applied for a part-time job to earn some working experiences. B ut I didn’t spend my time on any of them. I felt guilty whenever I looked back to the moments that I just sat around doing nothing. It’s said that better late than never. At least I had the consciousness that I should stop wasting my time. Making up my mind is the first step for me to learn to manage my time. Next, I wrote a timetable, setting some targets that I had to finish each day. For instance, on Monday, I must read two pieces of news and review all the lessons that I have learnt on that day. By the way, the daily plan that I made was flexible. If there’s something unexpected that I had to finish first, I would reduce the time for resting or delay my target to the next day. Also, I would try to achieve those targets ahead of time that I planed so that I could reserve some more time to relax or do something out of my plan. At the beginning, it’s kind of difficult to s tick to the plan. But as time went by, having a plan for time in advance became a part of my life. At the same time, I gradually became a well-organized person. Now I’ve grasped the time management skill and I’m able to use my time efficiently.
英语演讲稿：未来的工作 这篇《英语演讲稿范文：未来的工作》，是特地，希望对大家有所帮助！ 热门演讲推荐：竞聘演讲稿 | 国旗下演讲稿 | 英语演讲稿 | 师德师风演讲稿 | 年会主持词 | 领导致辞 everybody good afternoon:. first of all thank the teacher gave me a story in my own future ideal job. everyone has a dream job. my dream is to bee a boss, own a pany. in order to achieve my dreams, i need to find a good job, to accumulate some experience and wealth, it is the necessary things of course, in the school good achievement and rich knowledge is also very important. good achievement and rich experience can let me work to make the right choice, have more opportunities and achievements. at the same time, munication is very important, because it determines whether my pany has a good future development. so i need to exercise their municative ability. i need to use all of the free time to learn
小学生个人读书事迹简介怎么写800字 书,是人类进步的阶梯,苏联作家高尔基的一句话道出了书的重要。书可谓是众多名人的“宠儿”。历来,名人说出关于书的名言数不胜数。今天小编在这给大家整理了小学生个人读书事迹,接下来随着小编一起来看看吧! 小学生个人读书事迹1 “万般皆下品,惟有读书高”、“书中自有颜如玉,书中自有黄金屋”,古往今来,读书的好处为人们所重视,有人“学而优则仕”,有人“满腹经纶”走上“传道授业解惑也”的道路……但是,从长远的角度看,笔者认为读书的好处在于增加了我们做事的成功率,改善了生活的质量。 三国时期的大将吕蒙,行伍出身,不重视文化的学习,行文时,常常要他人捉刀。经过主君孙权的劝导,吕蒙懂得了读书的重要性,从此手不释卷,成为了一代儒将,连东吴的智囊鲁肃都对他“刮目相待”。后来的事实证明,荆州之战的胜利,擒获“武圣”关羽,离不开吕蒙的“运筹帷幄,决胜千里”,而他的韬略离不开平时的读书。由此可见,一个人行事的成功率高低,与他的对读书,对知识的重视程度是密切相关的。 的物理学家牛顿曾近说过,“如果我比别人看得更远,那是因为我站在巨人的肩上”,鲜花和掌声面前,一代伟人没有迷失方向,自始至终对读书保持着热枕。牛顿的话语告诉我们,渊博的知识能让我们站在更高、更理性的角度来看问题,从而少犯错误,少走弯路。
读书的好处是显而易见的,但是,在社会发展日新月异的今天,依然不乏对读书,对知识缺乏认知的人,《今日说法》中我们反复看到农民工没有和用人单位签订劳动合同,最终讨薪无果;屠户不知道往牛肉里掺“巴西疯牛肉”是犯法的;某父母坚持“棍棒底下出孝子”,结果伤害了孩子的身心,也将自己送进了班房……对书本,对知识的零解读让他们付出了惨痛的代价,当他们奔波在讨薪的路上,当他们面对高墙电网时,幸福,从何谈起?高质量的生活,从何谈起? 读书,让我们体会到“锄禾日当午,汗滴禾下土”的艰辛;读书,让我们感知到“四海无闲田,农夫犹饿死”的无奈;读书,让我们感悟到“为报倾城随太守,西北望射天狼”的豪情壮志。 读书的好处在于提高了生活的质量,它填补了我们人生中的空白,让我们不至于在大好的年华里无所事事,从书本中,我们学会提炼出有用的信息,汲取成长所需的营养。所以,我们要认真读书,充分认识到读书对改善生活的重要意义,只有这样,才是一种负责任的生活态度。 小学生个人读书事迹2 所谓读一本好书就是交一个良师益友,但我认为读一本好书就是一次大冒险,大探究。一次体会书的过程,真的很有意思,咯咯的笑声,总是从书香里散发;沉思的目光也总是从书本里透露。是书给了我启示,是书填补了我无聊的夜空,也是书带我遨游整个古今中外。所以人活着就不能没有书,只要爱书你就是一个爱生活的人,只要爱书你就是一个大写的人,只要爱书你就是一个懂得珍惜与否的人。可真所谓
常用兽药原粉药使用说明 抗生素类药物的选用 1、由革兰氏阳性菌引起的疾病，如猪丹毒、破伤风、炭疽、马腺疫、气肿疽、牛放线菌病、葡萄球菌性和链球菌性炎症、败血症等，可选用青霉素类、头孢菌素类、四环素类和大环内酯类、林可霉素等。 2、由革兰氏阴性菌引起疾病，如巴氏杆菌病、大肠杆菌病、沙门氏菌病、肠炎、泌尿道炎症，选用氨基糖苷类、氟喹诺酮类等。 3、由耐青霉素G 金黄色葡萄球菌所致呼吸道感染、败血症等，可选用耐青霉素酶的半合成青霉素，如苯唑西林、氯唑西林，也可选用大环内酯类和头孢菌素类抗生素。 4、由绿脓杆菌引起的创面及尿路感染、败血症、肺炎等，选用庆大霉素、多黏菌素等。 5、由支原体引起的猪喘气病和鸡慢性呼吸道病，则应首选氟喹诺酮类药，如恩诺沙星、红霉素、泰乐菌素、泰妙菌素等。 一.喹诺酮类： 1、氧氟沙星（纯粉）： （作用与用途）本品对多数革兰氏阴性、阳性菌、霉形体和某些厌氧菌有较强杀灭作用，主要用于治疗大肠杆菌病，霍乱、沙门氏菌病、慢性呼吸道病、鸭巴氏杆菌病等；（用法与用量）预防10g兑水200kg,冶疗100kg 1日2次，连用3-5天。 2、盐酸环丙沙星（纯粉） （作用与用途）本品是一种新型喹喏酮类、广谱、高效抗菌药。对各种细菌和霉形体均有强大的杀灭作用，尤其适用于细菌混合感染，主要用于鸡慢性呼吸道病、大肠杆菌、沙门氏菌、葡萄球菌、绿脓杆菌、霉形体及嗜血杆菌等细菌感染引起的消化道、呼吸道、肺部及全身炎症，临床上常作为消化道疾病用药。 （用法与用量）预防10克兑水100公斤，治疗50公斤，混料加倍，连用3-5天
3、乳酸环丙沙星（纯粉） 作用与用途）作用与用途同盐酸环丙沙星，其不同之处在于乳酸环丙沙星水溶性大大增强，吸收率高且吸收迅速，血药浓度高，因而治疗效果大大增强。 （用法与用量）同盐酸环丙沙星 4、氟哌酸（盐酸诺氟沙星）（纯粉） （作用与用途）本品属第三代喹诺酮类广谱抗菌药，高效，安全。主要用于大肠 杆菌、沙门氏菌、葡萄球菌、绿脓杆菌、霉形体及嗜血杆菌等细菌感染引起的消化道、呼吸道、肺部及全身炎症，临床上常作为消化道疾病用药。 （用法与用量）预防10克兑水100公斤，治疗50 公斤，混料加倍，连用3-5天 5、盐酸蒽诺沙星（纯粉） （作用与用途）本品为最新开发出的喹诺酮类药物之一，对各种细菌和霉形体有特效，本品的特点是广谱、高效、见效极快、杀菌彻底，有克菌王之称，是目前防治各种细菌病及霉形体病的特效药物。 （用法与用量）预防10克兑水100公斤，治疗50 公斤，混料加倍，连用3-5天 6、盐酸洛美沙星（纯粉） （作用与用途）本品是第三代喹诺酮类最新抗菌药，对各种细菌和霉形体有特效，口服吸收完全，用药后一小时就可达到有效杀菌浓度，见效极快，作用时间长达8小时，是目前治疗各种细菌病及鸡慢性呼吸道病的特效药物。 （用法与用量）预防10 克兑水200公斤，治疗兑水100公斤，连用3-5 天。 二、大环内脂类： 1、替米考星（纯品） 编辑版word
关于坚持的英语演讲稿 Results are not important, but they can persist for many years as a commemoration of. Many years ago, as a result of habits and overeating formed one of obesity, as well as indicators of overall physical disorders, so that affects my work and life. In friends to encourage and supervise, the participated in the team Now considered to have been more than three years, neither the fine rain, regardless of winter heat, a day out with 5:00 time. The beginning, have been discouraged, suffering, and disappointment, but in the end of the urging of friends, to re-get up, stand on the playground. 成绩并不重要，但可以作为坚持多年晨跑的一个纪念。多年前，由于庸懒习惯和暴饮暴食，形成了一身的肥胖，以及体检指标的全盘失常，以致于影响到了我的工作和生活。在好友的鼓励和督促下，参加了晨跑队伍。现在算来，已经三年多了，无论天晴下雨，不管寒冬酷暑，每天五点准时起来出门晨跑。开始时，也曾气馁过、痛苦过、失望过，但最后都在好友们的催促下，重新爬起来，站到了操场上。 In fact, I did not build big, nor strong muscles, not a sport-born people. Over the past few years to adhere to it, because I have a team behind, the strength of a strongteam here, very grateful to our team, for a long time, we encourage each other, and with sweat, enjoying common health happy. For example, Friends of the several run in order to maintain order and unable to attend the 10，000 meters race, and they are always concerned about the brothers and promptly inform the place and time, gives us confidence and courage. At the same time, also came on their own inner desire and pursuit for a good health, who wrote many of their own log in order to refuel for their own, and inspiring. 其实我没有高大身材，也没健壮肌肉，天生不属于运动型的人。几年来能够坚持下来，因为我的背后有一个团队，有着强大团队的力量，在这里，非常感谢我们的晨跑队，长期以来，我们相互鼓励着，一起流汗，共同享受着健康带来的快
1.How to build a business that lasts100years 0:11Imagine that you are a product designer.And you've designed a product,a new type of product,called the human immune system.You're pitching this product to a skeptical,strictly no-nonsense manager.Let's call him Bob.I think we all know at least one Bob,right?How would that go? 0:34Bob,I've got this incredible idea for a completely new type of personal health product.It's called the human immune system.I can see from your face that you're having some problems with this.Don't worry.I know it's very complicated.I don't want to take you through the gory details,I just want to tell you about some of the amazing features of this product.First of all,it cleverly uses redundancy by having millions of copies of each component--leukocytes,white blood cells--before they're actually needed,to create a massive buffer against the unexpected.And it cleverly leverages diversity by having not just leukocytes but B cells,T cells,natural killer cells,antibodies.The components don't really matter.The point is that together,this diversity of different approaches can cope with more or less anything that evolution has been able to throw up.And the design is completely modular.You have the surface barrier of the human skin,you have the very rapidly reacting innate immune system and then you have the highly targeted adaptive immune system.The point is,that if one system fails,another can take over,creating a virtually foolproof system. 1:54I can see I'm losing you,Bob,but stay with me,because here is the really killer feature.The product is completely adaptive.It's able to actually develop targeted antibodies to threats that it's never even met before.It actually also does this with incredible prudence,detecting and reacting to every tiny threat,and furthermore, remembering every previous threat,in case they are ever encountered again.What I'm pitching you today is actually not a stand-alone product.The product is embedded in the larger system of the human body,and it works in complete harmony with that system,to create this unprecedented level of biological protection.So Bob,just tell me honestly,what do you think of my product? 2:47And Bob may say something like,I sincerely appreciate the effort and passion that have gone into your presentation,blah blah blah-- 2:56(Laughter) 2:58But honestly,it's total nonsense.You seem to be saying that the key selling points of your product are that it is inefficient and complex.Didn't they teach you 80-20?And furthermore,you're saying that this product is siloed.It overreacts, makes things up as it goes along and is actually designed for somebody else's benefit. I'm sorry to break it to you,but I don't think this one is a winner.
关于工作的优秀英语演讲稿 Different people have various ambitions. Some want to be engineers or doctors in the future. Some want to be scientists or businessmen. Still some wish to be teachers or lawers when they grow up in the days to come. Unlike other people, I prefer to be a farmer. However, it is not easy to be a farmer for Iwill be looked upon by others. Anyway,what I am trying to do is to make great contributions to agriculture. It is well known that farming is the basic of the country. Above all, farming is not only a challenge but also a good opportunity for the young. We can also make a big profit by growing vegetables and food in a scientific way. Besides we can apply what we have learned in school to farming. Thus our countryside will become more and more properous. I believe that any man with knowledge can do whatever they can so long as this job can meet his or her interest. All the working position can provide him with a good chance to become a talent. 1 ————来源网络整理，仅供供参考
个人先进事迹简介 01 在思想政治方面,xxxx同学积极向上,热爱祖国、热爱中国共产党,拥护中国共产党的领导.利用课余时间和党课机会认真学习政治理论,积极向党组织靠拢. 在学习上,xxxx同学认为只有把学习成绩确实提高才能为将来的实践打下扎实的基础,成为社会有用人才.学习努力、成绩优良. 在生活中,善于与人沟通,乐观向上,乐于助人.有健全的人格意识和良好的心理素质和从容、坦诚、乐观、快乐的生活态度,乐于帮助身边的同学,受到师生的好评. 02 xxx同学认真学习政治理论,积极上进,在校期间获得原院级三好生,和校级三好生,优秀团员称号,并获得三等奖学金. 在学习上遇到不理解的地方也常常向老师请教,还勇于向老师提出质疑.在完成自己学业的同时,能主动帮助其他同学解决学习上的难题,和其他同学共同探讨,共同进步. 在社会实践方面,xxxx同学参与了中国儿童文学精品“悦”读书系,插画绘制工作,xxxx同学在班中担任宣传委员,工作积极主动,认真负责,有较强的组织能力.能够在老师、班主任的指导下独立完成学院、班级布置的各项工作. 03 xxx同学在政治思想方面积极进取,严格要求自己.在学习方面刻苦努力,不断钻研,学习成绩优异,连续两年荣获国家励志奖学金；作
为一名学生干部,她总是充满激情的迎接并完成各项工作,荣获优秀团干部称号.在社会实践和志愿者活动中起到模范带头作用. 04 xxxx同学在思想方面,积极要求进步,为人诚实,尊敬师长.严格 要求自己.在大一期间就积极参加了党课初、高级班的学习,拥护中国共产党的领导,并积极向党组织靠拢. 在工作上,作为班中的学习委员,对待工作兢兢业业、尽职尽责 的完成班集体的各项工作任务.并在班级和系里能够起骨干带头作用.热心为同学服务,工作责任心强. 在学习上,学习目的明确、态度端正、刻苦努力,连续两学年在 班级的综合测评排名中获得第1.并荣获院级二等奖学金、三好生、优秀班干部、优秀团员等奖项. 在社会实践方面,积极参加学校和班级组织的各项政治活动,并 在志愿者活动中起到模范带头作用.积极锻炼身体.能够处理好学习与工作的关系,乐于助人,团结班中每一位同学,谦虚好学,受到师生的好评. 05 在思想方面,xxxx同学积极向上,热爱祖国、热爱中国共产党,拥护中国共产党的领导.作为一名共产党员时刻起到积极的带头作用,利用课余时间和党课机会认真学习政治理论. 在工作上,作为班中的团支部书记,xxxx同学积极策划组织各类 团活动,具有良好的组织能力. 在学习上,xxxx同学学习努力、成绩优良、并热心帮助在学习上有困难的同学,连续两年获得二等奖学金. 在生活中,善于与人沟通,乐观向上,乐于助人.有健全的人格意 识和良好的心理素质.
香港正大生物制药 一.喹诺酮类： 氧氟沙星（纯粉）： （作用与用途）本品对多数革兰氏阴性、阳性菌、霉形体和某些厌氧菌有较强杀灭作用，主要用于治疗大肠杆菌病，霍乱、沙门氏菌病、慢性呼吸道病、鸭巴氏杆菌病等； （用法与用量）预防10g兑水200kg，冶疗100kg，1日2次，连用3-5天。 盐酸环丙沙星（纯粉） （作用与用途）本品是一种新型喹喏酮类、广谱、高效抗菌药。对各种细菌和霉形体均有强大的杀灭作用，尤其适用于细菌混合感染，主要用于鸡慢性呼吸道病、大肠杆菌、沙门氏菌、葡萄球菌、绿脓杆菌、霉形体及嗜血杆菌等细菌感染引起的消化道、呼吸道、肺部及全身炎症，临床上常作为消化道疾病用药。 （用法与用量）预防10克兑水100公斤，治疗50公斤，混料加倍，连用3-5天。 乳酸环丙沙星（纯粉） （作用与用途）作用与用途同盐酸环丙沙星，其不同之处在于乳酸环丙沙星水溶性大大增强，吸收率高且吸收迅速，血药浓度高，因而治疗效果大大增强。（用法与用量）同盐酸环丙沙星 氟哌酸（盐酸诺氟沙星）（纯粉） （作用与用途）本品属第三代喹诺酮类广谱抗菌药，高效，安全。主要用于大肠杆菌、沙门氏菌、葡萄球菌、绿脓杆菌、霉形体及嗜血杆菌等细菌感染引起的消化道、呼吸道、肺部及全身炎症，临床上常作为消化道疾病用药。 （用法与用量）预防10克兑水100公斤，治疗50公斤，混料加倍，连用3-5天。 盐酸蒽诺沙星（纯粉） （作用与用途）本品为最新开发出的喹诺酮类药物之一，对各种细菌和霉形体有特效，本品的特点是广谱、高效、见效极快、杀菌彻底，有克菌王之称，是目前防治各种细菌病及霉形体病的特效药物。 （用法与用量）预防10克兑水100公斤，治疗50公斤，混料加倍，连用3-5天。 盐酸洛美沙星（纯粉） （作用与用途）本品是第三代喹诺酮类最新抗菌药，对各种细菌和霉形体有特效，口服吸收完全，用药后一小时就可达到有效杀菌浓度，见效极快，作用时间长达8小时，是目前治疗各种细菌病及鸡慢性呼吸道病的特效药物。 （用法与用量）预防10克兑水200公斤，治疗兑水100公斤，连用3-5天。二、大环内脂类： 替米考星（纯品） （作用与用途）本品为泰乐菌素的高科技替代产品，对革兰氏阳性菌和支原体有很强的抗菌活性，临床主要用于畜禽呼吸道及猪的支原体肺炎（尤其是对鸡的败
尊敬的领导，老师，亲爱的同学们， 大家好！我是5班的梁浩东。今天早上我坐车来学校的路上，我仔细观察了路上形形色色的人，有开着小车衣着精致的叔叔阿姨，有市场带着倦容的卖各种早点的阿姨，还有偶尔穿梭于人群中衣衫褴褛的乞丐。于是我问自己，十几年后我会成为怎样的自己，想成为社会成功人士还是碌碌无为的人呢，答案肯定是前者。那么十几年后我怎样才能如愿以偿呢，成为一个受人尊重，有价值的人呢？正如我今天演讲的题目是：自主管理。 大家都知道爱玩是我们孩子的天性，学习也是我们的责任和义务。要怎样处理好这些矛盾，提高自主管理呢？ 首先，我们要有小主人翁思想，自己做自己的主人，要认识到我们学习，生活这一切都是我们自己走自己的人生路，并不是为了报答父母，更不是为了敷衍老师。 我认为自主管理又可以理解为自我管理，在学习和生活中无处不在，比如通过老师，小组长来管理约束行为和同学们对自身行为的管理都属于自我管理。比如我们到一个旅游景点，看到一块大石头，有的同学特别兴奋，会想在上面刻上：某某某到此一游话。这时你就需要自我管理，你需要提醒自己，这样做会破坏景点，而且是一种素质低下的表现。你设想一下，如果别人家小孩去你家墙上乱涂乱画，你是何种感受。同样我们把自主管理放到学习上，在我们想偷懒，想逃避，想放弃的时候，我们可以通过自主管理来避免这些，通过他人或者自己的力量来完成。例如我会制定作息时间计划表，里面包括学习，运动，玩耍等内容的完成时间。那些学校学习尖子，他们学习好是智商高于我们吗，其实不然，在我所了解的哪些优秀的学霸传授经验里，就提到要能够自我管理，规范好学习时间的分分秒秒，只有辛勤的付出，才能取得优异成绩。 在现实生活中，无数成功人士告诉我们自主管理的重要性。十几年后我想成为一位优秀的，为国家多做贡献的人。亲爱的同学们，你们们？让我们从现在开始重视和执行自主管理，十几年后成为那个你想成为的人。 谢谢大家！
关于工作的英语演讲稿 【篇一：关于工作的英语演讲稿】 关于工作的英语演讲稿 different people have various ambitions. some want to be engineers or doctors in the future. some want to be scientists or businessmen. still some wish to be teachers or lawers when they grow up in the days to come. unlike other people, i prefer to be a farmer. however, it is not easy to be a farmer for iwill be looked upon by others. anyway,what i am trying to do is to make great contributions to agriculture. it is well known that farming is the basic of the country. above all, farming is not only a challenge but also a good opportunity for the young. we can also make a big profit by growing vegetables and food in a scientific way. besides we can apply what we have learned in school to farming. thus our countryside will become more and more properous. i believe that any man with knowledge can do whatever they can so long as this job can meet his or her interest. all the working position can provide him with a good chance to become a talent. 【篇二：关于责任感的英语演讲稿】 im grateful that ive been given this opportunity to stand here as a spokesman. facing all of you on the stage, i have the exciting feeling of participating in this speech competition. the topic today is what we cannot afford to lose. if you ask me this question, i must tell you that i think the answer is a word---- responsibility. in my elementary years, there was a little girl in the class who worked very hard, however she could never do satisfactorily in her lessons. the teacher asked me to help her, and it was obvious that she expected a lot from me. but as a young boy, i was so restless and thoughtless, i always tried to get more time to play and enjoy myself. so she was always slighted over by me. one day before the final exam, she came up to me and said, could you please explain this to me? i can not understand it. i
常用兽药原粉药使用说明
常用兽药原粉药使用说明 抗生素类药物的选用 1、由革兰氏阳性菌引起的疾病，如猪丹毒、破伤风、炭疽、马腺疫、气肿疽、牛放线菌病、葡萄球菌性和链球菌性炎症、败血症等，可选用青霉素类、头孢菌素类、四环素类和大环内酯类、林可霉素等。 2、由革兰氏阴性菌引起疾病，如巴氏杆菌病、大肠杆菌病、沙门氏菌病、肠炎、泌尿道炎症，选用氨基糖苷类、氟喹诺酮类等。 3、由耐青霉素G金黄色葡萄球菌所致呼吸道感染、败血症等，可选用耐青霉素酶的半合成青霉素，如苯唑西林、氯唑西林，也可选用大环内酯类和头孢菌素类抗生素。 4、由绿脓杆菌引起的创面及尿路感染、败血症、肺炎等，选用庆大霉素、多黏菌素等。 5、由支原体引起的猪喘气病和鸡慢性呼吸道病，则应首选氟喹诺酮类药，如恩诺沙星、红霉素、泰乐菌素、泰妙菌素等。
一.喹诺酮类： 1、氧氟沙星（纯粉）： （作用与用途）本品对多数革兰氏阴性、阳性菌、霉形体和某些厌氧菌有较强杀灭作用，主要用于治疗大肠杆菌病，霍乱、沙门氏菌病、慢性呼吸道病、鸭巴氏杆菌病等； （用法与用量）预防10g兑水200kg，冶疗100kg，1日2次，连用3-5天。2、盐酸环丙沙星（纯粉） （作用与用途）本品是一种新型喹喏酮类、广谱、高效抗菌药。对各种细菌和霉形体均有强大的杀灭作用，尤其适用于细菌混合感染，主要用于鸡慢性呼吸道病、大肠杆菌、沙门氏菌、葡萄球菌、绿脓杆菌、霉形体及嗜血杆菌等细菌感染引起的消化道、呼吸道、肺部及全身炎症，临床上常作为消化道疾病用药。（用法与用量）预防10克兑水100公斤，治疗50公斤，混料加倍，连用3-5天。 3、乳酸环丙沙星（纯粉） （作用与用途）作用与用途同盐酸环丙沙星，其不同之处在于乳酸环丙沙星水溶性大大增强，吸收率高且吸收迅速，血药浓度高，因而治疗效果大大增强。（用法与用量）同盐酸环丙沙星 4、氟哌酸（盐酸诺氟沙星）（纯粉） （作用与用途）本品属第三代喹诺酮类广谱抗菌药，高效，安全。主要用于大肠杆菌、沙门氏菌、葡萄球菌、绿脓杆菌、霉形体及嗜血杆菌等细菌感染引起的消化道、呼吸道、肺部及全身炎症，临床上常作为消化道疾病用药。 （用法与用量）预防10克兑水100公斤，治疗50公斤，混料加倍，连用3-5天。 5、盐酸蒽诺沙星（纯粉） （作用与用途）本品为最新开发出的喹诺酮类药物之一，对各种细菌和霉形体有特效，本品的特点是广谱、高效、见效极快、杀菌彻底，有克菌王之称，是目前防治各种细菌病及霉形体病的特效药物。 （用法与用量）预防10克兑水100公斤，治疗50公斤，混料加倍，连用3-5天。