偏序关系
Multi tool use
偏序集合 (英语:P artially o rdered set ,简写poset )是数学中,特别是序理论中,指配备了部分排序关系的集合。
这个理論將排序、顺序或排列这个集合的元素的直觉概念抽象化。这种排序不必然需要是全部的,就是说不必要保证此集合内的所有对象的相互可比较性。部分排序集合定义了部分排拓扑。
目录
1 定义
1.1 非严格偏序,自反偏序
1.2 严格偏序,反自反偏序
1.3 偏序
1.4 偏序集与序对偶
1.5 完全性
2 例子
3 线性扩展
4 参见
5 引用
定义
非严格偏序,自反偏序
给定集合S,“≤”是S上的二元关系,若“≤”满足:
自反性 :∀a∈S,有a≤a;
反对称性 :∀a,b∈S,a≤b且b≤a,则a=b;
传递性 :∀a,b,c∈S,a≤b且b≤c,则a≤c;
则称“≤”是S上的非严格偏序 或自反偏序 。
严格偏序,反自反偏序
给定集合S,“<”是S上的二元关系,若“<”满足:
反自反性 :∀a∈S,有a≮a;
非对称性 :∀a,b∈S,a<b ⇒ b≮a;
传递性 :∀a,b,c∈S,a<b且b<c,则a<c;
则称“<”是S上的严格偏序 或反自反偏序 。
严格偏序与有向无环图(dag)有直接的对应关系。一个集合上的严格偏序的关系图就是一个有向无环图。其传递闭包是它自己。
偏序
容易证明以下结论:
给定集合S上的一个(非严格,自反)偏序「≤」,则可自然地诱导出S上的一个(严格,反自反)偏序「<」,只需如此定义:a < b,如果 a ≤ b 且 a ≠ b。
给定集合S上的一个(严格,反自反)偏序「<」,则可自然地诱导出S上的一个(非严格,自反)偏序「≤」,只需如此定义:a ≤ b,如果 a < b 或 a = b。
给定集合S上的一个(非严格,自反)偏序「≤」,其逆关系「≥」也是S上的一个(非严格,自反)偏序;
给定集合S上的一个(严格,反自反)偏序「<」,其逆关系「>」也是S上的一个(严格,反自反)偏序;
由上述可知,只要定义了「≤」、「<」、「≥」、「>」中的任何一个,其余三个关系的定义可以自然诱导而出,这四种关系实际上可以看成一体。故此在不严格区分的情况下,只需定义其一即可(通常是「≤」),称之为集合S上的偏序关系 。(“偏序关系”通常被用来称呼非严格偏序关系。)
(非严格,自反)偏序和(严格,反自反)偏序之间的对应关系不同于在(非严格)弱序和严格弱序直接的对应(逆关系的补集)。只有对于全序这些对应才是相同的。
偏序集与序对偶
若集合S上定义了一个偏序,则S称为偏序集 (poset );若将其上的偏序关系改为其逆关系,得到的新偏序集S'称为S的序对偶 。
虽然通常术语“有序集”用来称呼全序集,但当上下文中不涉及其他序关系时,“有序集”也可用于称呼偏序集。
完全性
例子
下面是一些主要的例子:
自然数的集合配备了它的自然次序(小于等于关系)。这个偏序是全序。
自然数的集合的有限子集{1, 2, ..., n }。这个偏序是全序。
一般的说偏序集合的两个元素x 和y 可以处于四个相互排斥的关联中任何一个:要么x < y ,要么x = y ,要么x > y ,要么x 和y 是“不可比较”的(三个都不是)。全序集合是用规则排除第四种可能的集合:所有元素对都是可比较的,并且声称三分法成立。自然数、整数、有理数和实数都关于它们代数(有符号)大小是全序的,而复数不是。这不是说复数不能全序排序;比如我们可以按词典次序排序它们,通过x +i y < u +i v 当且仅当x < u 或(x = u 且y < v ),但是这种排序没有合理的大小意义因为它使得1大于100i 。按绝对大小排序它们产生在其中所有对都是可比较的预序,但这不是偏序因为1和i 有相同的绝对大小但却不相等,违反了反对称性。
线性扩展
全序T 是偏序P 的线性扩展 ,只要x ≤ y 在P 中成立则x ≤ y 在T 中也成立。在计算机科学中,找到偏序的线性扩展的算法叫做拓扑排序。
参见
引用
J. V. Deshpande, On Continuity of a Partial Order , Proceedings of the American Mathematical Society, Vol. 19, No. 2, 1968, pp. 383-386
ZB5xBngFQ42 uCdgs mlB5W1ViTjXg19zKdB
Popular posts from this blog
提示 :本条目的主题不是 香港中文大學(深圳) 。 body.skin-minerva .mw-parser-output table.infobox caption{text-align:center} 香港中文大學 The Chinese University of Hong Kong 校训 博文約禮 [1] [2] 创建时间 1963年10月17日 学校类型 法定(公立)、研究型 監督 主權移交前:英屬香港總督 主權移交後:香港特別行政區行政長官 校董會主席 梁乃鵬博士 校長 段崇智教授 副校长 華雲生教授(常務副校長) 霍泰輝教授、吳基培教授 張妙清教授、潘偉賢教授 陳偉儀教授、吳樹培先生 教师人數 1,619 [3] 学生人數 25,489 [3] 本科生人數 20,147 [3] 研究生人數 5,342 [3] 校址 香港新界沙田馬料水沙田市地段437號(大埔公路十一至十二咪左右(正門及崇基門) 22°25′10″N 114°12′19″E / 22.41946°N 114.205358°E / 22.41946; 114.205358 坐标: 22°25′10″N 114°12′19″E / 22.41946°N 114.205358°E / 22.41946; 114.205358 科學園路與澤祥街交界(東校門) 澤祥街18號(沙田凱悅酒店及工商管理學院)) 校區 新市鎮 总面积 134.4公頃(1,344,000平方米) [2] 代表色 紫與金 [1] 吉祥物 鳳凰 [1] 隶属 英聯邦大學協會 國際商管學院促進協會(AACSB) 東南亞高等教育協會 ( 英语 : ASAIHL ) 國際大學協會 亚太高校书院联盟 八大公立大學聯盟(譯自:HK8)[3] 网站 http://www.cuhk.edu.hk/ 香港中文大學 ( 英语: The Chinese University of Hong Kong ,縮寫为 CUHK ),簡稱 中文大學 、 中大...
10
1
I have a function that searches a vector of iterators and returns the iterator if its names matches a string passed as an argument. koalaGraph::PVertex lookUpByName(std::string Name, std::vector<koalaGraph::PVertex>& Vertices) { for (size_t i = 0; i < Vertices.size(); i++) { if(Vertices[i]->info.name == Name) return Vertices[i]; } } My question is how can I implement this as a lambda, to use it in connection with std::find_if ? I'm trying this: std::vector<koalaGraph::PVertex> V; std::string Name; std::find_if(V.begin(), V.end(), [&Name]() {return Name == V->info.name;}) But it says that V an enclosing-function local variable cannot be referenced in a lambda body unless it is in the capture list.
...
坐标: 23°33′53″N 119°33′50″E / 23.564832°N 119.563924°E / 23.564832; 119.563924 澎湖天后宮 澎湖天后宮山門與廟埕 漢語拼音 tiān hòu gōng 台羅拼音 má tsóo king 基本資訊 所在地 中華民國(臺灣) 澎湖縣馬公市長安里正義街1號 創建年份 不明 大明萬曆32年(1604年)之前 開基者 不明 廟格 闔澎公廟 本殿構造 五開間三進落 等級 國定古蹟 主神 天上聖母 例祭 農曆正月元宵、七月普渡 相关人物 沈有容、韋麻郎、施琅、藍木、黃良、陳玉峰 澎湖天后宮 中華民國(臺灣)文化資產 登錄名稱 澎湖天后宮 其他名稱 媽祖宮、娘媽宮、天妃宮 登錄等級 國定第一級古蹟 登錄類別 祠廟 登錄公告日期 1983年12月28日 開放時間 07:00 --17:00 材質 紅磚、土黃色花崗岩、泉州白石與黑色石階 參觀費用 免費參觀 所有權者 開台澎湖天后宮管理委員會 澎湖天后宮 ,位於台灣澎湖縣馬公市,闔澎公廟之一,主祀天上聖母媽祖,台灣歷史最悠久的廟宇。天后宮確切創建年代眾說紛紜,隨著「沈有容諭退紅毛番韋麻郎等」石碑出土,確定於大明萬曆卅二年(1604年)即已立廟。 [1] :48-53 天后宮早無定稱,稱 娘娘宮 、 天妃宮、娘媽宮、媽祖宮 或 媽宮 等稱呼在所多有。清朝領有台灣後,施琅宣稱克台戰役多賴天妃顯靈襄助,奏請康熙皇帝加封,晉天妃為天后,故今稱「天后宮」。 [2] :8-13 目录 1 沿革 1.1 明朝及明鄭時期 1.2 清領時期 1.3 日治時期 1.4 中華民國 2 奉祀 2.1 媽祖、千里眼、順風耳 2.2 註生娘娘 2.3 送子觀音 2.4 至聖先師 2.5 積慶公夫婦 2.6 天津媽祖像 2.7 虎爺 3 建築歷史 ...