Home

ようこそ、キタムラの内へ。

ミュージックの世界へ

英雄伝説-碧の軌跡-最果て神樹 (Original ver.)

About

Hello Guys!

Blog

[星幽的黄昏] I. prologue

沃斯塔里奥睁开了双眼。 熟悉的天顶,熟悉的床铺。窗外的天空也如同帝国都市给人的感觉一样是一片灰暗。 鲁斯本帝国,是克里斯基大陆上唯一一个横贯东西的国家。帝国的开国元勋——托斯卡纳 · 奥莱恩二世,在连年的外交侵略和战争恐吓下打下了帝国今日的疆土。这也使得鲁斯本帝国成为了克里斯基大陆上最为强大的国家。帝国的北部临接着阿肯山脉,在阿肯山脉的西北部坐落着沃肯湖群,而琳斯卡帝国就坐落在沃肯湖群一旁。 在帝国的东北方,坐落着亚礼士提亚帝国。作为临接沃肯湖群、阿肯山脉和阶降林的国家,亚礼士提亚是唯一一个拥有足够的资本与鲁斯本帝国进行抗衡的国家。正因如此,阿肯山脉东部的气氛永远比山顶之寒亦冷。 路维西卡(鲁斯卡纳语意:东部的阶降之城)是帝国的第五大都市。第一名,毋庸置疑是坐落于帝国中央的希斯西卡(鲁斯卡纳语意:至高的阶降之城);而路维西卡作为第五大都市,掌管了帝国整个东部的命脉。可以说,掌握了路维西卡,就是扼住了鲁斯本帝国军事的咽喉。 远处若隐若现的炮声并没有吓到沃斯塔里奥。 “今天依旧是这样啊,亚礼士提亚。分明隔着一座山脉,谁也无法越过这条天然防线,但总是要做做样子表示自己宣誓主权的意愿、吗。”沃斯咬了一口手上的面包,开始看起了今天的报纸。 突然,一条信息吸引了沃斯的视线: “急报:帝国战线终向沃肯山脉推进到古尔流孚(亚礼士提亚南部都市)。” 沃斯差点被噎住;“这…这不应该是做做样子而已吗?帝国在过去几百年里那么多次尝试向沃肯山脉推进,却终究因为环境与补给不易的原因没有成功;现在并不是帝国最强盛的时候,为何帝国能够一下推进那么远?” 正当沃斯狐疑之时,远方传来了胜利的号角,并且愈来愈近了。是的,这一定是帝国东部战线的凯歌;已经有多少年没有听到过这旋律了,沃斯心想。但为什么、是现在?为什么、是凯歌? 军队的气势告诉了沃斯,斯达尔坎(帝国沃肯山脉与亚礼士提亚接壤都市,有争议)收复了。帝国从亚礼士提亚手里夺回了多年以来牵挂的故土。作为一名帝国人,心中自然充满了喜悦;但是为什么呢?沃斯很疑惑。 沃斯塔里奥的本职是水晶雕刻工匠。不说是路维西卡的一把手,也是路维西卡当中排的上号的人物。在这个世界当中,水晶是一切协同作用的来源;曾经有一些人们说要抛弃水晶而使用煤炭、或是从地中的黑色液体(原油),但屈服于水晶强大的协同作用,那些提案被一一抛弃。在这个世界,水晶就是硬通货。 水晶雕刻工匠是水晶处理这一行当当中排位最高的。在他之下又有水晶炼官,水晶炼用师、水晶校验工匠、水晶探别工匠与水晶实业者。他们分别管理水晶高度协同化、水晶协同化、水晶等级分析与品质分析、水晶拓扑探测与水晶开采的工作。在这个世界当中,一些特殊的雕刻能与水晶协调作用带来不可思议的效果;其据说是“来自上天的直接神迹”。水晶匠人地位之高,如此可见一斑。

【图论】学习笔记(五)

以下我们定义一下图相同。 图相同,顾名思义,就是表示两张图拥有相同的状态。因此,我们并不把图相同叫做图相同而是叫做同态(isomorphic)。 定义: 如果两张图存在以下一种一一隐射:f: V(G) →V(H),且对于G中任意两点u、v,他们是毗连的当且仅当图H中的两点f(u)与f(v)是毗连的。在这种情况下,我们说图G、H为同态图(isomorphic graph)。我们把这样的f叫做G到H的同态。记作G≌H。 显然我们马上就能推出以下结论: 1、自反性,G≌G 2、对称性,G≌H,则H≌G 3、传递性,G≌H,H≌Q,则G≌Q 同态图还有以下的性质: 1、v(G)=v(H) 2、e(G)=e(H) 我们来介绍一下度数列(degree sequence)的概念。度数列就是将一张图中所有的顶点的度数列出来。一般而言,我们会将他换位排成降序。由此我们能发现: 对于G≌H,我们有G和H的度数列相等。 相对的我们就能够推出若GH的度数列不相等,则G!≌H。 接下来我们来讲讲子图(subgraph)的问题。 以下先给出子图的定义: 一张图H,若满足V(H)⊆V(G),E(H)⊆E(G),则H就是G的子图。 其中若H与G不是同态则称为H是G的真(proper)子图。 当V(H)=V(G)且H是G的子图时,我们称H是对G跨越的(spanning)。 为了探索子图与图的关系,我们以下定义: 对于图G与R,定义nG(R)为G与R同态的子图的数量。即在G中,有一部分子图,是与R同态的,这些子图的数量就被定义为nG(R)。 显然对于同态图GH,我们有nG(R)=nH(R) 相对应的,如果存在图R使得nG(R)≠nH(R),则GH必然不同态。 如下我们给出归纳图的定义。 对于G,他的一个子图H,如果对于G、H相对应的任意顶点u、v、f(u)、f(v),假设G中uv连接存在,则在H图中f(u)f(v)连接存在;满足这样条件的子图H被称为G的归纳图(induced graph)。我们也说H由其顶点集V(H)归纳而来,记作H=[V(H)]。 接下来我们来考虑归纳图的充要条件。 一张子图W是图G的子图当且仅当W=G-(V(G)\V(W))。其中V(G)\V(W)代表V(W)在V(G)中的补集。 接下来我们介绍一下重建猜想(reconstruction conjecture)。 我们先给出重建性的定义: 我们给出图G,V(G)={u1, u2, …. un}。当对于任意一张拥有n个顶点的图H,V(H)={v1, v2, ……vn},满足对于任意对应的顶点,我们有H-vi同态于G-ui,且能得到H同态于G,那我们说G是可重建(reconstructible)的。(注意,这里代表G被他的n幅子图G-u1, G-u2, …G-un唯一确定。) 那么就能得到重建猜想(未证明): 对于任意三阶及以上的图,都是可重建的。 在结尾非常不负责任的猜测,这个猜想的证明可能会大量与群论和规约相关;并且最后会用到第二数学归纳法。

【图论】学习习题(一)

1、G为(n,m)图,证明:δ(G)<=2m/n<=△(G) 注意到2m=∑dG(v),而δ(G)=mind(v), △(G)=maxd(v), 放缩有v(G)×δ(G)<=∑dG(v)<=v(G)×△(G) 两边同时除以v(G)=n,即得到结论。 2、令G为(n,2n)图,且n>=5。证明:G为4级正规或者存在一点z使得d(z)>=5。 若G为正规图,则由∑d(v)=2×e(G)知d(v)=4n/n=4,即G为4级正规。 若G不是正规图,即至少存在一对d(i),d(j),其中d(i)>4 d(j)<4。 若不然,则G为正规图或者不符合题设。 我们令d(j)为d(z),则有d(z)>=5。 3、让G为正规相连非完全图,证明:对于任意顶点x,存在一个顶点w使得d(x, w)=2。 已知G为正规图,且G非完全,则有d(v)为常数且d(v)<2e(G)/v(G) 因为G是相连的,任意两顶点x,w必然能够找到一条道路相连。对于任意x,w,此处我们只需要找到一个顶点连接了x,w就能够证明结论。那我们假设对于任意两点i,j,我们找不到这样一个顶点连接他们两个。 首先我们知道在此题中1-正规图一定不成立(不相连),让我们考虑2-正规图。 显然,2-正规图可以化成一个“环”,即将所有的边写成如下形式: (v1, v2), (v2, v3), ….., (vn-1, vn), (vn, v1) 我们能找到对于vk,有k`=k±2 mod n,使得d(k, k`)=2。 接下来我们考察3-正规图。显然,3-正规图中一定会包括我们上述的2-正规图的情况。否则我们可以说至少存在一组(vk, vk+1)是不存在连接的。则显然,如若如此,d(vk)与d(vk+1)需要另外找点来满足其正规图的性质。则原本1条连接变为了两条且不存在另找点使得连接总数不变的情况,因此矛盾。我们得出3-正规图一定会包含2-正规图。 如此假设对n=k,k-1,k-2….3正规图成立,我们考虑n=k+1正规图。 同样的,k正规图中能够规约到2-正规图,因此能够找到d(x, w)=2。假设k+1正规图找不到,则k+1正规图不包括k正规图。即,我们在k+1正规图中找不到这样一个子图,使得对于每一个顶点v,恰好有k-1个顶点与其连接。 但是我们知道在k+1正规图中,对于每一个顶点v,恰好有k个顶点与其连接。则这个k+1正规图只能由非正规图加线条构成,即k,k-1,k-2…..正规图加线条无法构成k+1正规图。但是我们取k-1正规图,对于任意顶点,连接他边上一个顶点我们就构成了一个k+1正规图。矛盾。 由此得到n-正规图都包括2-正规图,因此可以得到d(x, w)=2。 4、我们来讲讲n-cube图。 令n-cube图包括以下顶点: x1x2x3…xn,xk∈{0, 1}。 当两个顶点的各位数数据,有且仅有一个不同时,他们毗连。 很容易发现,v(Qn)=2^n 由于Qn各顶点构成n项1,0的全排列,易知对于任意顶点,与他仅有一位数据不同的顶点有且仅有n项。 因此Qn为n-正规图。 显然,e(Qn)=n×2^(n-1),rad(Qn)=diam(Qn)=n(就是与此顶点完全不同的那个顶点) 由于对称性可以知道C(Qn)就是其中所有的顶点。

ようこそ、キタムラの内へ。