当前位置：文档库 › On the space requirement of interval routing

On the space requirement of interval routing

HKU CSIS Tech Report TR-96-11

On the Space Requirement of Interval Routing

Savio S.H.Tse and Francis https://www.wendangku.net/doc/0c978513.html,u

Department of Computer Science

The University of Hong Kong

sshtse,fcmlau@cs.hku.hk

December1996

Abstract

Interval routing is a space-ef?cient method for point-to-point networks.It

is based on labeling the edges of a network with intervals of node numbers

(called interval labels).An-label scheme allows up to labels to be put on

an edge.Intuitively,the larger is,the better the quality of(i.e.,shorter)the

paths thus generated.For arbitrary graphs of size,the number of nodes,

the problem is to determine the minimum necessary for achieving optimal-

ity in the length of the longest path.The longest path(maximum of all shortest

paths)resulted from a labeling is an important indicator of the performance of

any algorithm that runs on the network.We argue that the problem is not ap-

plicable to graphs whose diameter()is insigni?cant(e.g.,a small constant)

with respect to.Our result is an improved lower bound on—for

Index Terms—Compact routing,computational complexity,computer net-

works,distributed systems,graph theory,interval routing,optimization,short-

est paths.

Correspondence:https://www.wendangku.net/doc/0c978513.html,u,Department of Computer Science,The University of Hong Kong,

Hong Kong/Email:fcmlau@cs.hku.hk/Fax:(+852)25598447

1Introduction

Interval routing was ?rst proposed by Santoro and Khatib [6],and subsequently re?ned by van Leeuwen and Tan [10].The idea is to label the nodes by integers (called node numbers)from a cyclicly ordered set,say,

,where is the number of nodes;and the edges by intervals of the form ,where are node numbers.

is the set if ,or if .is the short form for ,i.e.,the set .During routing,a message is routed along an edge whose interval label contains the destination node number,until the message reaches the destination.An example of interval routing is shown in Figure 1.The ?gure shows the routing path of a message that travels from Node

a message destined for Node 0

Figure 1:An example of interval routing

to Node 0.The message ?rst takes the edge to Node 3because 0is contained in the interval ,and then takes the edge to Node 4because is contained in ,and so on.Clearly,with interval routing,at most space is needed at a node,where is the node’s degree.In general,is smaller than ,the size of the network,and we say that the routing information stored at a node as required by interval routing is “compact”.See the survey by Tan and van Leeuwen [7]for an overview of the ?eld of compact routing.

One of the main questions in interval routing research is that given ,how to label its nodes and edges so that all the routing paths are shortest paths,where represents either a speci?c kind of graphs or arbitrary graphs (general networks).A successful labeling satisfying the condition constitutes an optimum interval routing

scheme(IRS).For a number of speci?c graphs,optimum IRSs are known to exist [7].What about arbitrary graphs?Ruˇz iˇc ka answered this in the negative way by constructing a graph that has no optimum IRS[5].

What then can be done if indeed no optimum IRS exists for a given network? One possibility is to relax the requirement of compactness of routing information by allowing more than one interval label to be associated with an edge.An IRS that allows up to labels per edge is called an-label IRS,or simply-IRS.Figure2 shows a graph which has no optimum1-label IRS,as proved by Fraigniaud and Gavoille[1],but has optimum IRS if up to two labels per edge are allowed.One such optimum2-IRS for the graph is shown in the?gure.In the?gure,some edges have one label,while the others have two.

Figure2:A circular-arc graph and its optimum2-label IRS

Because of the existence of graphs like the one just shown,multi-label interval routing has become an interesting branch of interval routing research.The central theme is to?nd a good trade-off between routing information storage(in terms of number of labels per edge)and the path lengths.In[2],Gavoille and Guˇe vremont proved that at least labels per edge are needed for shortest-path interval rout-ing in some general networks.In[9],Tse and Lau proved that in order to have an IRS with the longest path shorter than,where is the diameter,la-bels per edge are needed;and to have an IRS with the longest path shorter than, labels per edge are needed.In[4],Kr′aˇloviˇc,Ruˇz iˇc ka andˇStefankoviˇc proved

the same result—a lower bound of labels per edge—but the associated lower bound on the longest path was improved to.1Recently,Gavoille further im-proved the lower bound on the number of labels,to[3];the lower bound on the longest path remains as.In this paper,we propose a new lower bound on the number of labels per edge needed for any optimal IRS.The bound is which is applicable to networks where.Unfortunately,even using this many labels,the longest path still falls short of being optimal.The lower bound on the longest path we prove is,where.Our results suggest that it is not practical to impose optimality on the routing paths for arbitrary graphs using interval routing.

Note that we target our pursuit of a new bound on the space requirement at graphs whose diameter is a signi?cant parameter—in general,a function of,as op-posed to a constant.Graphs whose diameter is suf?ciently small belong to the cat-egory of dense graphs.The construction of dense graphs is an active area in graph theory research.A dense graph has a small diameter,usually a small degree,but a large order(number of nodes)—for example,there exists a degree-10graph having 47059200nodes but whose diameter is only10[11].For dense graphs having a small diameter,the labeling algorithm by Santoro and Khatib[6],which generates paths that are bounded by is very near the best(i.e.,)one can hope for,where is the diameter.Their algorithm uses at most one label for an edge.Even if we allow more labels(up to say)to be used per edge,one cannot do better than reduc-ing the bound on the(longest)path length to[3].As is so insigni?cant as compared to,the reduction by really cannot justify the cost due to the extra labels,not to mention the insigni?cance of the reduced length itself.Therefore,it is not meaningful to pursue after a multi-label labeling scheme for dense graphs or graphs whose diameter is a small constant.The more meaningful question then is: What is the minimum number of labels needed per edge in order to achieve the op-timal longest path length—i.e.,that equaling and is some function of?This paper answers this question.

1Their bound on the longest path is best for number of labels ranging from to.

2Properties

The network in question is a connected graphs,,where is the set of nodes,and the set of the edges.Every edge in is bidirectional.There are nodes in.To implement interval routing,each node is labeled with a node number,from the set.

Every edge in each direction is labeled with interval labels,each of the form ,where.For that are directly connected,

denote the interval labels for the edge that goes from to.For convenience,we use as a short-hand notation for

A node is said to be contained in if(1)for,or(2)

or,otherwise.We use the notation,to denote the cyclic ordering of node numbers,for.Naturally,. As in[8],the expression means that and are contained in some interval and that they are ordered after and before,but the order of and is not shown.

Property1(Completeness)The set of interval labels for edges directed from a node is complete.That is,every node in must be contained in one of’s interval.

Property2(No ambiguity)The interval labels for edges directed from a node are disjoint. That is,for,is contained in exactly one of these intervals.

Property3(No bouncing)For each,there exists no node,such that is contained in both and.

It should be noted that these properties are necessary but not suf?cient for a valid IRS.A valid IRS is one that can route a message from any node to any other node.

For-IRS(),Property2seems to be unnecessary for the set of labels that are associated with the same outgoing edge.It is,however,not practical to have

multiple such labels that are overlapping,for they should be combined into a single label,thus saving some space.In fact,an-IRS allows a stronger kind of disjoint-ness for the multiple labels associated with an edge—that is,there could exist a gap between the labels’intervals such that they cannot be concatenated to form a single interval.

3The Lower Bounds

Fact3.1On distributing elements into buckets,there exists one bucket containing at least elements;and there exist buckets each containing not more than ele-ments.

We now present the graph based on which we will derive our lower bound on the number of labels.

De?ne which is of size

and diameter,where are positive integers,and and are as follows.

An example of for,,and is shown in Figure3.has ?aps whose roots are the nodes;each?ap has columns and layers.We use the subscripts to index a?ap,a column,and a layer, respectively.

3.1Flap,Layer and Slice

In our main proof(Theorem3.1),we will arrive at a contradiction which is against an assumption about the longest path.The assumption is that there exists an-IRS for such that the longest path is shorter than.Now,if this assumption is true,then the following lemmas and corollaries would hold.

Figure3:The skeleton of for and.

Lemma3.1For each?ap,there exist at most disjoint intervals which contain but not any elements in.

Proof:Consider.A routing path from to must begin with the edge ;otherwise,the routing path(beginning with any other edge)is at least of length.Hence,.If these intervals also con-tain,where,for any,then the routing path from to this via the edge will have a length of at least.

Corollary3.1For each?ap,there exist at most disjoint intervals which con-tain but not any elements in

Proof:Direct consequence of Lemma3.1.

We call the disjoint intervals in the above corollary for a given?ap?ap inter-vals which cover all the?ap’s even columns()spanning up to the -th layer.

Lemma3.2For each layer,there exist at most disjoint intervals which contain but not any elements in.

Proof:Consider,and the proof is similar to that of Lemma3.1.

Corollary3.2For each layer,there exist at most disjoint intervals which contain but not any elements in

Proof:Direct consequence of Lemma3.2.

We call the disjoint intervals in the above corollary for a given layer layer in-tervals which cover those elements within the layer that are at even columns of all the?aps except the last?ap().

The elements covered in Corollary3.1and3.2constitute the set

which is made up of all the even columns in the?rst layers of the?rst?aps.In the following,we concentrate on this set.The elements of this set form a cyclic structure of intervals.The union of all the?ap intervals cover exactly the set;sim-ilarly for the layer intervals.In fact,the?aps and the layers represent two views of the set(see Figure4).There is a third view,which is based on something which we call a slice.

For,de?ne

is a slice.

Lemma3.3For each slice,there exist at most disjoint intervals which contains but not any elements in,.

Proof:Assume there exist at least disjoint intervals containing,but not any elements in,,such that without loss of generality the following cyclic structure of intervals is true.

where the subscripts indicate the number of each type of intervals.There are disjoint intervals which contain.Hence,without loss of generality,there are at least disjoint intervals which contain but not,where

and .And so we have the following

cyclic structure of intervals.

Consider

,where .By the assumption about the longest path,the routing from to any element in will pass through the edge ,and the the routing from to any element in will pass

through the edge .Hence,will be covered by the disjoint in-terval labels on the edge and

by those on the edge .By Property 2,these two sets of intervals cannot overlap;therefore,it is impossible to realize the cyclic structure of intervals as shown above.

We call those intervals introduced in the above lemma slice intervals .

3.2The Main Results

Referring to Figure 4which shows the set

being viewed in three different ways,as ?aps,as layers,and as

slices.A ?ap has elements,a layer elements,and a slice

elements.A number of flaps u

A number of layers A number of slices

u Figure 4:Three views of the set .

Given some interval ,we refer to those elements at the margins of the interval as marginal elements,and the remaining elements non-marginal elements.If has only one element,then the element is a marginal element.An inter-?ap interval is one that contains two or more marginal nodes belonging to different ?ap intervals,and nothing else.Similarly,we have inter-layer and inter-slice intervals.Figure 5shows some examples of these kinds of intervals.Note that some of these “inter”intervals can be of more than one kind,as shown in the ?gure.Figure 6highlights

the relationship between slice intervals and inter-slice intervals;the other two kinds of relationships are similar.

A non-marginal element An element in B

A slice

A layer

A flap Figure 5:A simpli?ed interval structure of

the set .

Figure 6:Example of slice intervals and inter-slice intervals.

Theorem 3.1There is a graph such that for any valid

-IRS,the longest routing path will be no shorter than ,where is the diameter.

Proof:By Lemma 3.3,we have at most

slice intervals for each slice,and there are slices.Hence,we have at most intervals for all slices,and therefore at most

elements belonging to inter-slice intervals (Figure 6).These elements are dis-tributed among layers.By Fact 3.1,there exist

layers each containing at most elements which belong to inter-slice intervals.That means each of these lay-ers contains at least elements not belonging to inter-slice intervals.By Corollary 3.2,each layer has at most layer intervals,and an interval has at most

two marginal elements.Therefore,in these layers,we have at least

elements not belonging to inter-slice intervals and which are non-marginal elements of some layer interval.These elements are the non-marginal elements of inter-?ap intervals(Figure7).2These intervals are indeed inter-?ap intervals(they satisfy the de?nition of inter-?ap interval)because as layer intervals their elements must be contiguous within the cyclic structure of intervals and therefore each element can only be the marginal element of some?ap interval.Since there are at least such

Figure7:A layer and its layer intervals.

layers,we have a total of

non-marginal elements of some inter-?ap intervals,or more.By Fact3.1,there exists a?ap which has at least

non-marginal elements of some inter-?ap intervals.Let,, and.Substituting,the above becomes

which is.

2Note that the?gure could include for example inter-slice intervals that span multiple layers;then the parts of these intervals that belong to the layer shown would appear as ordinary“?at”layer in-tervals.

As a result,these non-marginal elements of the?ap in question cannot be grouped into or fewer disjoint intervals,which is in contradiction with Corollary3.1,and hence the assumption about the longest path cannot be true.

Next,we give the main results of this paper.

Theorem3.2There is a graph,with diameter,such that if the length of ev-ery path is to be bounded by,the lower bound on the number of labels needed per edge is .

Proof:Referring to the proof of Theorem3.1,the graph is of size

Also,it is not dif?cult to see that in the above,.Since, we have.

We can push the numbers further by extending the graph.We modify the graph such that each edge is replaced by the chain of nodes

by the chain of nodes

and by the chain of nodes

for all.

Theorem3.3There is a graph with such that by using not more than labels per edge,the longest path cannot be shorter than,where.

Proof:The graph is the extended graph above,which has a size of

and diameter.Obviously,Theorem3.1is still valid after the modi?-cation.3Substituting into the result of Theorem3.1,the

lower bound follows.

Substituting the values of,,and the value of,we have

Hence,.

From the above,we have.By Theorem3.2,the maximum value of is;therefore,.Since,.

4Conclusion

The contribution of this paper is the derivation of a new lower bound on the number of labels needed for achieving optimal routing paths in arbitrary networks based on interval routing.The bound is for,which is an improvement over the previous bound of for.[3].It appears that the space requirement of interval routing for some arbitrary graphs is substantial,and it is not practical to impose optimality on the routing paths for these graphs.

3Simply change the edge to in the proof of Lemma3.1,and to and to in the proof of Lemma3.3.

References

[1]P.Fraigniaud,P and C.Gavoille,Interval Routing Schemes,Research Re-

port No.94-04,Laboratoire de L’Informatique du Parallˇe lism,Ecole Normale Supˇe rieure de Lyon,France,1994.

[2]C.Gavoille,C.and E.Guˇe vremont,Worst Case Bounds for Shortest Path In-

terval Routing.Research Report No.95-02,Laboratoire de L’Informatique du Parallˇe lism,Ecole Normale Supˇe rieure de Lyon,France,1995.

[3]C.Gavoille,On Dilation of Interval Routing,Research Report RR-1145-96,

LaBRI,University of Bordeaux,France,November1996.

[4]R.Kr′aˇloviˇc,P.Ruˇz iˇc ka,D.ˇStefankoviˇc,The Complexity of Shortest Path and

Dilation Bounded Interval Routing,Technical Report,Department of Com-puter Science,Comenius University,August1996.

[5]P.Ruˇz iˇc ka,A Note on The Ef?ciency of An Interval Routing Algorithm,The

Computer Journal,34(1991)475–476.

[6]N.Santoro and R.Khatib,Labelling and Implicit Routing in Networks,The

Computer Journal,28(1985)5–8.

[7]R.B.Tan and J.van Leeuwen,Compact Routing Methods:A Survey,Technical

Report RUU-CS-95-05,Dept.of Computer Science,Utrecht University,1995.

(Also in Proceedings of Colloquium on Structural Information Information and Com-munication Complexity(SICC’94)(1994)99–109.)

[8]S.S.H.Tse and https://www.wendangku.net/doc/0c978513.html,u,A Lower Bound for Interval Routing in General Net-

works,Networks,to appear.

[9]S.S.H.Tse and https://www.wendangku.net/doc/0c978513.html,u,Two Lower Bounds for Mult-Label Interval Routing,

Proceedings of Computing:The Australasian Theory Symposium(CATS’97),Syd-ney,Australia,February1997,to appear.

[10]J.van Leeuwen and R.B.Tan,Interval Routing,The Computer Journal,30(1987)

298–307.

[11]Table of Largest(Degree,Diameter)-Graphs,maintained by Department of

Applied Mathematics and Telematics,Universitat Polit`e cnica de Catalunya, Spain,URL:http://maite71.upc.es/grup de grafs/table g.html.

on the contrary的解析

On the contrary Onthecontrary, I have not yet begun. 正好相反，我还没有开始。 https://www.wendangku.net/doc/0c978513.html, Onthecontrary, the instructions have been damaged. 反之，则说明已经损坏。 https://www.wendangku.net/doc/0c978513.html, Onthecontrary, I understand all too well. 恰恰相反，我很清楚 https://www.wendangku.net/doc/0c978513.html, Onthecontrary, I think this is good. ⑴我反而觉得这是好事。 https://www.wendangku.net/doc/0c978513.html, Onthecontrary, I have tons of things to do 正相反，我有一大堆事要做 Provided by jukuu Is likely onthecontrary I in works for you 反倒像是我在为你们工作 https://www.wendangku.net/doc/0c978513.html, Onthecontrary, or to buy the first good. 反之还是先买的好。 https://www.wendangku.net/doc/0c978513.html, Onthecontrary, it is typically american. 相反，这正是典型的美国风格。 222.35.143.196 Onthecontrary, very exciting.

恰恰相反，非常刺激。 https://www.wendangku.net/doc/0c978513.html, But onthecontrary, lazy. 却恰恰相反，懒洋洋的。 https://www.wendangku.net/doc/0c978513.html, Onthecontrary, I hate it! 恰恰相反，我不喜欢！ https://www.wendangku.net/doc/0c978513.html, Onthecontrary, the club gathers every month. 相反，俱乐部每个月都聚会。 https://www.wendangku.net/doc/0c978513.html, Onthecontrary, I'm going to work harder. 我反而将更努力工作。 https://www.wendangku.net/doc/0c978513.html, Onthecontrary, his demeanor is easy and nonchalant. 相反，他的举止轻松而无动于衷。 https://www.wendangku.net/doc/0c978513.html, Too much nutrition onthecontrary can not be absorbed through skin. 太过营养了反而皮肤吸收不了. https://www.wendangku.net/doc/0c978513.html, Onthecontrary, I would wish for it no other way. 正相反，我正希望这样 Provided by jukuu Onthecontrary most likely pathological. 反之很有可能是病理性的。 https://www.wendangku.net/doc/0c978513.html, Onthecontrary, it will appear clumsy. 反之，就会显得粗笨。 https://www.wendangku.net/doc/0c978513.html,

英语造句

一般过去式时间状语：yesterday just now (刚刚) the day before three days ag0 a week ago in 1880 last month last year 1. I was in the classroom yesterday. I was not in the classroom yesterday. Were you in the classroom yesterday. 2. They went to see the film the day before. Did they go to see the film the day before. They did go to see the film the day before. 3. The man beat his wife yesterday. The man didn’t beat his wife yesterday. 4. I was a high student three years ago. 5. She became a teacher in 2009. 6. They began to study english a week ago 7. My mother brought a book from Canada last year. 8.My parents build a house to me four years ago . 9.He was husband ago. She was a cooker last mouth. My father was in the Xinjiang half a year ago. 10.My grandfather was a famer six years ago. 11.He burned in 1991

学生造句--Unit 1

●I wonder if it’s because I have been at school for so long that I’ve grown so crazy about going home. ●It is because she wasn’t well that she fell far behind her classmates this semester. ●I can well remember that there was a time when I took it for granted that friends should do everything for me. ●In order to make a difference to society, they spent almost all of their spare time in raising money for the charity. ●It’s no pleasure eating at school any longer because the food is not so tasty as that at home. ●He happened to be hit by a new idea when he was walking along the riverbank. ●I wonder if I can cope with stressful situations in life independently. ●It is because I take things for granted that I make so many mistakes. ●The treasure is so rare that a growing number of people are looking for it. ●He picks on the weak mn in order that we may pay attention to him. ●It’s no pleasure being disturbed whena I settle down to my work. ●I can well remember that when I was a child, I always made mistakes on purpose for fun. ●It’s no pleasure accompany her hanging out on the street on such a rainy day. ●I can well remember that there was a time when I threw my whole self into study in order to live up to my parents’ expectation and enter my dream university. ●I can well remember that she stuck with me all the time and helped me regain my confidence during my tough time five years ago. ●It is because he makes it a priority to study that he always gets good grades. ●I wonder if we should abandon this idea because there is no point in doing so. ●I wonder if it was because I ate ice-cream that I had an upset student this morning. ●It is because she refused to die that she became incredibly successful. ●She is so considerate that many of us turn to her for comfort. ●I can well remember that once I underestimated the power of words and hurt my friend. ●He works extremely hard in order to live up to his expectations. ●I happened to see a butterfly settle on the beautiful flower. ●It’s no pleasure making fun of others. ●It was the first time in the new semester that I had burned the midnight oil to study. ●It’s no pleasure taking everything into account when you long to have the relaxing life. ●I wonder if it was because he abandoned himself to despair that he was killed in a car accident when he was driving. ●Jack is always picking on younger children in order to show off his power. ●It is because he always burns the midnight oil that he oversleeps sometimes. ●I happened to find some pictures to do with my grandfather when I was going through the drawer. ●It was because I didn’t dare look at the failure face to face that I failed again. ●I tell my friend that failure is not scary in order that she can rebound from failure. ●I throw my whole self to study in order to pass the final exam. ●It was the first time that I had made a speech in public and enjoyed the thunder of applause. ●Alice happened to be on the street when a UFO landed right in front of her. ●It was the first time that I had kept myself open and talked sincerely with my parents. ●It was a beautiful sunny day. The weather was so comfortable that I settled myself into the

英语句子结构和造句

高中英语~词性~句子成分~语法构成第一章节：英语句子中的词性 1.名词：n. 名词是指事物的名称，在句子中主要作主语.宾语.表语.同位语。 2.形容词;adj. 形容词是指对名词进行修饰~限定~描述~的成份，主要作定语.表语.。形容词在汉语中是（的）.其标志是: ous. Al .ful .ive。. 3.动词：vt. 动词是指主语发出的一个动作，一般用来作谓语。 4.副词：adv. 副词是指表示动作发生的地点. 时间. 条件. 方式. 原因. 目的. 结果.伴随让步. 一般用来修饰动词. 形容词。副词在汉语中是（地）.其标志是：ly。 5.代词：pron. 代词是指用来代替名词的词，名词所能担任的作用，代词也同样.代词主要用来作主语. 宾语. 表语. 同位语。 6.介词：prep.介词是指表示动词和名次关系的词，例如：in on at of about with for to。其特征：

介词后的动词要用—ing形式。介词加代词时，代词要用宾格。例如：give up her（him）这种形式是正确的，而give up she（he）这种形式是错误的。 7.冠词：冠词是指修饰名词，表名词泛指或特指。冠词有a an the 。 8.叹词：叹词表示一种语气。例如：OH. Ya 等 9.连词：连词是指连接两个并列的成分，这两个并列的成分可以是两个词也可以是两个句子。例如：and but or so 。 10.数词：数词是指表示数量关系词，一般分为基数词和序数词第二章节：英语句子成分主语：动作的发出者，一般放在动词前或句首。由名词. 代词. 数词. 不定时. 动名词. 或从句充当。谓语：指主语发出来的动作，只能由动词充当，一般紧跟在主语后面。宾语：指动作的承受着，一般由代词. 名词. 数词. 不定时. 动名词. 或从句充当. 介词后面的成分也叫介词宾语。定语：只对名词起限定修饰的成分，一般由形容

六级单词解析造句记忆MNO

M A: Has the case been closed yet? B: No, the magistrate still needs to decide the outcome. magistrate n.地方行政官，地方法官，治安官 A: I am unable to read the small print in the book. B: It seems you need to magnify it. magnify vt.１．放大，扩大；２．夸大，夸张 A: That was a terrible storm. B: Indeed, but it is too early to determine the magnitude of the damage. magnitude n.１．重要性，重大；２．巨大，广大 A: A young fair maiden like you shouldn’t be single. B: That is because I am a young fair independent maiden. maiden n.少女，年轻姑娘，未婚女子 a.首次的，初次的 A: You look majestic sitting on that high chair. B: Yes, I am pretending to be the king! majestic a.雄伟的，壮丽的，庄严的，高贵的 A: Please cook me dinner now. B: Yes, your majesty, I’m at your service. majesty n.１．［Ｍ－］陛下（对帝王，王后的尊称）；２．雄伟，壮丽，庄严 A: Doctor, I traveled to Africa and I think I caught malaria. B: Did you take any medicine as a precaution? malaria n.疟疾 A: I hate you! B: Why are you so full of malice? malice n.恶意，怨恨 A: I’m afraid that the test results have come back and your lump is malignant. B: That means it’s serious, doesn’t it, doctor? malignant a.１．恶性的，致命的；２．恶意的，恶毒的 A: I’m going shopping in the mall this afternoon, want to join me? B: No, thanks, I have plans already. mall n.（由许多商店组成的）购物中心 A: That child looks very unhealthy. B: Yes, he does not have enough to eat. He is suffering from malnutrition.

base on的例句

意见应以事实为根据. 3 来自辞典例句 192. The bombers swooped ( down ) onthe air base. 轰炸机突袭空军基地. 来自辞典例句 193. He mounted their engines on a rubber base. 他把他们的发动机装在一个橡胶垫座上. 14 来自辞典例句 194. The column stands on a narrow base. 柱子竖立在狭窄的地基上. 14 来自辞典例句 195. When one stretched it, it looked like grey flakes on the carvas base. 你要是把它摊直, 看上去就象好一些灰色的粉片落在帆布底子上. 18 来自辞典例句 196. Economic growth and human well - being depend on the natural resource base that supports all living systems. 经济增长和人类的福利依赖于支持所有生命系统的自然资源. 12 1 来自辞典例句 197. The base was just a smudge onthe untouched hundred - mile coast of Manila Bay. 那基地只是马尼拉湾一百英里长安然无恙的海岸线上一个硝烟滚滚的污点. 6 来自辞典例句 198. You can't base an operation on the presumption that miracles are going to happen. 你不能把行动计划建筑在可能出现奇迹的假想基础上.

英语造句大全

英语造句大全English sentence 在句子中，更好的记忆单词！ 1、(1)、able adj. 能句子：We are able to live under the sea in the future. (2)、ability n. 能力句子：Most school care for children of different abilities. (3)、enable v. 使。。。能句子：This pass enables me to travel half-price on trains. 2、(1)、accurate adj. 精确的句子：We must have the accurate calculation. (2)、accurately adv. 精确地句子：His calculation is accurately. 3、(1)、act v. 扮演句子：He act the interesting character. （2）、actor n. 演员句子：He was a famous actor. (3)、actress n. 女演员句子：She was a famous actress. (4)、active adj. 积极的句子：He is an active boy. 4、add v. 加句子：He adds a little sugar in the milk. 5、advantage n. 优势句子：His advantage is fight. 6、age 年龄n. 句子：His age is 15. 7、amusing 娱人的adj. 句子：This story is amusing. 8、angry 生气的adj. 句子：He is angry. 9、America 美国n.

(完整版)主谓造句

主语+谓语 1. 理解主谓结构 1) The students arrived. The students arrived at the park. 2) They are listening. They are listening to the music. 3) The disaster happened. 2．体会状语的位置 1) Tom always works hard. 2) Sometimes I go to the park at weekends.. 3) The girl cries very often. 4) We seldom come here. The disaster happened to the poor family. 3. 多个状语的排列次序 1) He works. 2) He works hard. 3) He always works hard. 4) He always works hard in the company. 5) He always works hard in the company recently. 6) He always works hard in the company recently because he wants to get promoted. 4. 写作常用不及物动词 1. ache My head aches. I’m aching all over. 2. agree agree with sb. about sth. agree to do sth. 3. apologize to sb. for sth. 4. appear (at the meeting, on the screen) 5. arrive at / in 6. belong to 7. chat with sb. about sth. 8. come (to …) 9. cry 10. dance 11. depend on /upon 12. die 13. fall 14. go to … 15. graduate from 16. … happen 17. laugh 18. listen to... 19. live 20. rise 21. sit 22. smile 23. swim 24. stay (at home / in a hotel) 25. work 26. wait for 汉译英： 1.昨天我去了电影院。 2.我能用英语跟外国人自由交谈。 3.晚上7点我们到达了机场。 4.暑假就要到了。 5.现在很多老人独自居住。 6.老师同意了。 7.刚才发生了一场车祸。 8.课上我们应该认真听讲。9. 我们的态度很重要。 10. 能否成功取决于你的态度。 11. 能取得多大进步取决于你付出多少努力。 12. 这个木桶能盛多少水取决于最短的一块板子的长度。

初中英语造句

【it's time to和it's time for】 ——————这其实是一个句型,只不过后面要跟不同的东西. ——————It's time to跟的是不定式（to do）.也就是说,要跟一个动词,意思是“到做某事的时候了”.如： It's time to go home. It's time to tell him the truth. ——————It's time for 跟的是名词.也就是说,不能跟动词.如： It's time for lunch.(没必要说It's time to have lunch) It's time for class.(没必要说It's time to begin the class.) They can't wait to see you Please ask liming to study tonight. Please ask liming not to play computer games tonight. Don’t make/let me to smoke I can hear/see you dance at the stage You had better go to bed early. You had better not watch tv It’s better to go to bed early It’s best to run in the morning I am enjoy running with music. With 表伴随听音乐 I already finish studying You should keep working. You should keep on studying English Keep calm and carry on 保持冷静继续前行二战开始前英国皇家政府制造的海报名字 I have to go on studying I feel like I am flying I have to stop playing computer games and stop to go home now I forget/remember to finish my homework. I forget/remember cleaning the classroom We keep/percent/stop him from eating more chips I prefer orange to apple I prefer to walk rather than run I used to sing when I was young What’s wrong with you There have nothing to do with you I am so busy studying You are too young to na?ve I am so tired that I have to go to bed early

The Kite Runner-美句摘抄及造句

《The Kite Runner》追风筝的人--------------------------------美句摘抄 1.I can still see Hassan up on that tree, sunlight flickering through the leaves on his almost perfectly round face, a face like a Chinese doll chiseled from hardwood: his flat, broad nose and slanting, narrow eyes like bamboo leaves, eyes that looked, depending on the light, gold, green even sapphire 翻译：我依然能记得哈桑坐在树上的样子，阳光穿过叶子，照着他那浑圆的脸庞。他的脸很像木头刻成的中国娃娃，鼻子大而扁平，双眼眯斜如同竹叶，在不同光线下会显现出金色、绿色，甚至是宝石蓝。 E.g.: A shadow of disquiet flickering over his face. 2.Never told that the mirror, like shooting walnuts at the neighbor's dog, was always my idea. 翻译：从来不提镜子、用胡桃射狗其实都是我的鬼主意。E.g.:His secret died with him, for he never told anyone. 3.We would sit across from each other on a pair of high

翻译加造句

一、翻译 1. The idea of consciously seeking out a special title was new to me., but not without appeal. 让我自己挑选自己最喜欢的书籍这个有意思的想法真的对我具有吸引力。 2.I was plunged into the aching tragedy of the Holocaust, the extraordinary clash of good, represented by the one decent man, and evil. 我陷入到大屠杀悲剧的痛苦之中，一个体面的人所代表的善与恶的猛烈冲击之中。 3.I was astonished by the the great power a novel could contain. I lacked the vocabulary to translate my feelings into words. 我被这部小说所包含的巨大能量感到震惊。我无法用语言来表达我的感情（心情）。 4，make sth. long to short长话短说 5.I learned that summer that reading was not the innocent(简单的) pastime(消遣) I have assumed it to be., not a breezy, instantly forgettable escape in the hammock(吊床)，( though I’ ve enjoyed many of those too ). I discovered that a book, if it arrives at the right moment, in the proper season, will change the course of all that follows. 那年夏天，我懂得了读书不是我认为的简单的娱乐消遣，也不只是躺在吊床上，一阵风吹过就忘记的消遣。我发现如果在适宜的时间、合适的季节读一本书的话，他将能改变一个人以后的人生道路。二、词组造句 1. on purpose 特意，故意 This is especially true here, and it was ~. (这一点在这里尤其准确，并且他是故意的) 2.think up 虚构，编造，想出 She has thought up a good idea. 她想出了一个好的主意。 His story was thought up. 他的故事是编出来的。 3. in the meantime 与此同时助记：in advance 事前in the meantime 与此同时in place 适当地... In the meantime, what can you do? 在这期间您能做什么呢？ In the meantime, we may not know how it works, but we know that it works. 在此期间，我们不知道它是如何工作的，但我们知道，它的确在发挥作用。 4.as though 好像，仿佛 It sounds as though you enjoyed Great wall. 这听起来好像你喜欢长城。 5. plunge into 使陷入 He plunged the room into darkness by switching off the light. 他把灯一关，房

改写句子练习2标准答案

The effective sentences:(improve the sentences!) 1.She hopes to spend this holiday either in Shanghai or in Suzhou. 2.Showing/to show sincerity and to keep/keeping promises are the basic requirements of a real friend. 3.I want to know the space of this house and when it was built. I want to know how big this house is and when it was built. I want to know the space of this house and the building time of the house. 4.In the past ten years,Mr.Smith has been a waiter,a tour guide,and taught English. In the past ten years,Mr.Smith has been a waiter,a tour guide,and an English teacher. 5.They are sweeping the floor wearing masks. They are sweeping the floor by wearing masks. wearing masks,They are sweeping the floor. 6.the drivers are told to drive carefully on the radio. the drivers are told on the radio to drive carefully 7.I almost spent two hours on this exercises. I spent almost two hours on this exercises. 8.Checking carefully,a serious mistake was found in the design. Checking carefully,I found a serious mistake in the design.

用以下短语造句

M1 U1 一. 把下列短语填入每个句子的空白处（注意所填短语的形式变化）： add up (to) be concerned about go through set down a series of on purpose in order to according to get along with fall in love (with) join in have got to hide away face to face 1 We’ve chatted online for some time but we have never met ___________. 2 It is nearly 11 o’clock yet he is not back. His mother ____________ him. 3 The Lius ___________ hard times before liberation. 4 ____________ get a good mark I worked very hard before the exam. 5 I think the window was broken ___________ by someone. 6 You should ___________ the language points on the blackboard. They are useful. 7 They met at Tom’s party and later on ____________ with each other. 8 You can find ____________ English reading materials in the school library. 9 I am easy to be with and _____________my classmates pretty well. 10 They __________ in a small village so that they might not be found. 11 Which of the following statements is not right ____________ the above passage? 12 It’s getting dark. I ___________ be off now. 13 More than 1,000 workers ___________ the general strike last week. 14 All her earnings _____________ about 3,000 yuan per month. 二.用以下短语造句： 1.go through 2. no longer/ not… any longer 3. on purpose 4. calm… down 5. happen to 6. set down 7. wonder if 三. 翻译： 1.曾经有段时间，我对学习丧失了兴趣。（there was a time when…） 2. 这是我第一次和她交流。（It is/was the first time that …注意时态） 3.他昨天公园里遇到的是他的一个老朋友。（强调句） 4. 他是在知道真相之后才意识到错怪女儿了。（强调句） M 1 U 2 一. 把下列短语填入每个句子的空白处（注意所填短语的形式变化）： play a …role (in) because of come up such as even if play a …part (in) 1 Dujiangyan(都江堰) is still ___________in irrigation(灌溉) today. 2 That question ___________ at yesterday’s meeting. 3 Karl Marx could speak a few foreign languages, _________Russian and English. 4 You must ask for leave first __________ you have something very important. 5 The media _________ major ________ in influencing people’s opinion s. 6 _________ years of hard work she looked like a woman in her fifties. 二.用以下短语造句： 1.make (good/full) use of 2. play a(n) important role in 3. even if 4. believe it or not 5. such as 6. because of

英语造句

English sentence 1、(1)、able adj. 能句子：We are able to live under the sea in the future. (2)、ability n. 能力句子：Most school care for children of different abilities. (3)、enable v. 使。。。能句子：This pass enables me to travel half-price on trains. 2、(1)、accurate adj. 精确的句子：We must have the accurate calculation. (2)、accurately adv. 精确地句子：His calculation is accurately. 3、(1)、act v. 扮演句子：He act the interesting character.（2）、actor n. 演员句子：He was a famous actor. (3)、actress n. 女演员句子：She was a famous actress. (4)、active adj. 积极的句子：He is an active boy. 4、add v. 加句子：He adds a little sugar in the milk. 5、advantage n. 优势句子：His advantage is fight. 6、age 年龄n. 句子：His age is 15. 7、amusing 娱人的adj. 句子：This story is amusing. 8、angry 生气的adj. 句子：He is angry. 9、America 美国n. 句子：He is in America. 10、appear 出现v. He appears in this place. 11. artist 艺术家n. He is an artist. 12. attract 吸引 He attracts the dog. 13. Australia 澳大利亚 He is in Australia. 14.base 基地 She is in the base now. 15.basket 篮子 His basket is nice. 16.beautiful 美丽的 She is very beautiful. 17.begin 开始 He begins writing. 18.black 黑色的 He is black. 19.bright 明亮的 His eyes are bright. 20.good 好的 He is good at basketball. 21.British 英国人 He is British. 22.building 建造物 The building is highest in this city 23.busy 忙的 He is busy now. 24.calculate 计算 He calculates this test well. 25.Canada 加拿大 He borns in Canada. 26.care 照顾 He cared she yesterday. 27.certain 无疑的 They are certain to succeed. 28.change 改变 He changes the system. 29.chemical 化学药品